线段树专题—ZOJ1610 Count the Colors

题意：给一个n，代表n次操作，接下来每次操作表示把[l。r]区间的线段涂成k的颜色当中,l,r,k的范围都是0到8000

分析：事实上就是拿线段树维护一段区间的颜色，整体用到的是线段树的区间更新把，可是会给人一种区间合并的错觉

注意：这题比較坑的是千万不能拿n建树，不然就会segmentation fault，必须拿8000建树。也就是树是固定的

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 1e4+5;

int col[maxn<<2];

int num[maxn];

int ncol;

void down(int l,int r,int rt){

    if(col[rt]!=-1){

        col[rt<<1]=col[rt<<1|1]=col[rt];

        col[rt]=-1;

    }

}

void update(int L,int R,int k,int l,int r,int rt){

    if(L<=l&&r<=R){

        col[rt]=k;

        return;

    }

    down(l,r,rt);

    int mid=(l+r)>>1;

    if(L<=mid) update(L,R,k,l,mid,rt<<1);

    if(R>mid) update(L,R,k,mid+1,r,rt<<1|1);

}

void query(int l,int r,int rt){

    if(l==r){

        if(col[rt]>=0&&col[rt]!=ncol) num[col[rt]]++; //统计连续颜色段的个数

        ncol=col[rt];

        return;

    }

    down(l,r,rt);

    int mid=(l+r)>>1;

    query(l,mid,rt<<1);

    query(mid+1,r,rt<<1|1);

}

int main()

{

    int n;

    while(scanf("%d",&n)!=-1){

        ncol=-1;

        memset(num,0,sizeof(num));

        memset(col,-1,sizeof(col));  //建树

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

            int c,l,r;

            scanf("%d%d%d",&l,&r,&c);

            if(l<r) update(l+1,r,c,1,8000,1);

        }

        query(1,8000,1);

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

            if(num[i]) printf("%d %d\n",i,num[i]);

        }

        printf("\n");

    }

}