zoj 1610 Count the Colors[セグメントツリー]

#include<cstring>// ， ， 
#include<cstdio>
using namespace std;
#define lson    l,m,rt<<1
#define rson    m,r,rt<<1|1
struct node{int l,r,col;};
const int maxn=8008;
node no[maxn<<2];
int col[maxn<<2];//   .
int res[maxn<<2];//  .
void init(){    // ...
    memset(no,0,sizeof(no));
    memset(col,-1,sizeof(col));
}
void pushdown(int rt){  // .
    if(no[rt].col>=0){
        no[rt<<1].col=no[rt<<1|1].col=no[rt].col;
        no[rt].col=-1;     // 
    }
}
void build(int l,int r,int rt){ // 
    no[rt].l=l;
    no[rt].r=r;
    no[rt].col=-1;
    if(l==r-1)    return;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}
void update(int p,int l,int r,int rt){ // . 
    if(no[rt].l>=l&&r>=no[rt].r) {
        // x1,x2 .
        no[rt].col=p;
        return ;
    }
    if(no[rt].col==p) return;// 
    pushdown(rt);   // 
    int m=(no[rt].l+no[rt].r)>>1;
    if(l>=m)
        update(p,l,r,rt<<1|1);
    else if(r<=m)
        update(p,l,r,rt<<1);
    else {
        update(p,lson);
        update(p,rson);
    }
}
void query(int l,int r,int rt){ // ， col .
    if(no[rt].col>=0){
        for(int i=l;i<r;i++)
            col[i]=no[rt].col;
        return ;
    }
    if(no[rt].l==no[rt].r-1) return ;
    int m=(no[rt].l+no[rt].r)>>1;
    if(l>=m)    query(l,r,rt<<1|1);
    else if(r<=m)   query(l,r,rt<<1);
    else {
        query(lson);
        query(rson);
    }
}
int main(){
    int n,x1,x2,c;
    while(~scanf("%d",&n)){
        init();
        build(0,maxn,1);
        while(n--){
            scanf("%d%d%d",&x1,&x2,&c);
            update(c,x1,x2,1);
        }
        query(0,maxn,1);// 
		memset(res,0,sizeof(res));
		for(int i=0;i<maxn;i++){
			if(col[i+1]!=col[i]&&col[i]!=-1){
				res[col[i]]++;
			}
		}
        for(int i=0;i<maxn;i++) {
            if(res[i]) printf("%d %d
",i,res[i]);
        }
        printf("
");
    }
    return 0;
}