傳說中的區間染色問題
看了好幾個區間染色問題，也問了神犇，目測只有暴力的方法啊。。
這道題是因為只詢問一次，所以比較好搞，不用維護父節點有多少種顏色。。
先用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;
}
