ZOJ 1610 Count the Colors

传说中的区间染色问题

看了好几个区间染色问题，也问了神犇，目测只有暴力的方法啊。。

这道题是因为只询问一次，所以比较好搞，不用维护父节点有多少种颜色。。

先用update pushdown 记录该节点是否被单一颜色覆盖了，如果是记录该颜色（c）

如果不是设置成-1就行了

pushup函数就是看两个子节点是否颜色相同，相同就更新父节点，不同父节点就-1

全部操作完了以后把每一个叶子节点的颜色都推出来，然后算一边就行了。。。

这题需要注意的是，染色是不包括端点的，需要把坐标乘以2（l*2,r*2-1），

另外color初始化要X*4 不要X（调了好久才发现= =）

代码：

[cpp]
#include<stdio.h>
#define lson l,mid,rt*2
#define rson mid+1,r,rt*2+1
#define X 16010
int color[X*4],ll,rr,c;
int as[X],f[X];
void pushup(int rt){
    color[rt]=color[rt*2]==color[rt*2+1]?color[rt*2]:-1;
}
void pushdown(int rt){
    if(color[rt]>=0){
        color[rt*2]=color[rt*2+1]=color[rt];
        color[rt]=-1;
    }
}
void update(int l,int r,int rt){
    if(ll<=l&&rr>=r){
        color[rt]=c;
        return ;
    }
    int mid=l+r>>1;
    pushdown(rt);
    if(ll<=mid)update(lson);
    if(rr> mid)update(rson);
    pushup(rt);

}
void solve(int l,int r,int rt){
    if(l==r){f[l]=color[rt];return ;}
    pushdown(rt);
    int mid=l+r>>1;
    solve(lson);
    solve(rson);
}
int main(){
    int i,j,n;
    while(~scanf("%d",&n)){
        for(i=0;i<X*4;i++)color[i]=-1;
        for(i=0;i<X;i++){
            as[i]=0;
            f[i]=-1;
        }
        for(i=0;i<n;i++){
            scanf("%d%d%d",&ll,&rr,&c);
            ll*=2;rr=rr*2-1;
            update(0,X,1);
        }
        solve(0,X,1);
        for(i=0;i<X;i++)
            if(f[i]!=f[i+1]&&f[i]>=0)
                as[f[i]]++;
        for(i=0;i<X;i++)
            if(as[i])
                printf("%d %d\n",i,as[i]);
        puts("");
    }
    return 0;
}

补充：软件开发 , C++ ,