Count the Colors ZOJ - 1610

线段树区间染色求染色的片段数

#include <cstdio>

#include <iostream>

#include <queue>

#include <cmath>

#include <algorithm>

#include <cstring>

using namespace std;

#define ll long long

#define P pair<int,int>

const ll INF=1e18;

const int N=8000+10;

int ans[N];

struct SegmentTree{

    int l,r;

    int dat;

}t[N*4];

void build(int p,int l,int r)

{

    t[p].l = l;

    t[p].r = r;

    t[p].dat = -1;

    if(t[p].l == t[p].r){t[p].dat = -1;return ;}

    int mid = (l+r)/2;

    build(p*2,l,mid);

    build(p*2+1,mid+1,r);

}

void spread(int p)

{

    if(t[p].dat>=0)

    {

        t[p*2].dat = t[p].dat;

        t[p*2+1].dat = t[p].dat;

        t[p].dat = -1;

    }

}

void change(int p,int l,int r,int v)

{

    if(l <= t[p].l && t[p].r <= r)

    {

        t[p].dat = v;

        return ;

    }

    int mid = (t[p].l+t[p].r)/2;

    spread(p);

    if(l<=mid) change(p*2,l,r,v);

    if(r>mid) change(p*2+1,l,r,v);

}

int ask(int p,int l,int r)

{

    if(t[p].l == t[p].r)

    {

        return t[p].dat;

    }

    int mid = (t[p].l+t[p].r)/2;

    spread(p);

    if(l<=mid) return ask(p*2,l,r);

    if(r>mid) return ask(p*2+1,l,r);

}

int n;

int main()

{

    ios::sync_with_stdio(false);

    while(cin >> n)

    {

        build(1,1,8000);

        for(int i=0;i<=8000;i++)

        {

            ans[i] = 0;

        }

        for(int i=1;i<=n;i++)

        {

            int l,r,d;

            cin >> l >> r >> d;

            change(1,l+1,r,d);

        }

        int last = -1,now;

        for(int i=1;i<=8000;i++)

        {

            now = ask(1,i,i);

            if(now!=last && now!=-1)

                ans[now]++;

            last = now;

        }

        for(int i=0;i<=8000;i++)

        {

            if(ans[i])

            {

                cout << i <<" "<< ans[i] <<"\n";

            }

        }

        cout << "\n";

    }

    return 0;

}
巴特西

线段树区间染色 ZOJ 1610

Count the Colors ZOJ - 1610

线段树区间染色求染色的片段数

最新文章

热门文章
