poj 2777 Count Color (线段树)

#include<iostream> #include<math.h> #include<cstdio> #include<stdlib.h> #include<cstring> using namespace std; #define MAXN 100010 /* update是把一个区间内颜色相同的改成相同颜色 颜色不同为-1 query 是查询函数，如果颜色不是-1，就把这个颜色记录为1 最后所有在这个区间的颜色都加一起 */ struct node { int l,r,s; }t[MAXN<<2]; int L,O,T; int sum[33]; void build(int l,int r,int i) { t[i].l=l; t[i].r=r; t[i].s=1; if(l==r)return ; int mid =(l+r)>>1; build(l,mid,i<<1); build(mid+1,r,i<<1|1);//就是i*2+1 } void update(int l, int r, int m, int i) { if(t[i].s == m) return ; if(t[i].l == l && t[i].r == r) { t[i].s = m; return ; } if(t[i].s != -1) { t[i<<1].s = t[i<<1|1].s = t[i].s; t[i].s = -1; } int mid = (t[i].l+t[i].r)>>1; if(l > mid) update(l, r, m, i<<1|1); else if(r <= mid) update(l, r, m, i<<1); else { update(l, mid, m, i<<1); update(mid+1, r, m, i<<1|1); } } void query(int l, int r, int i) { if(t[i].s != -1)//如果纯色把该颜色标记 { sum[t[i].s] = 1; return ; } else//否则继续查询子节点 { int mid = (t[i].l+t[i].r)>>1; if(l > mid) query(l, r, i<<1|1); else if(r <= mid) query(l, r, i<<1); else { query(l, mid, i<<1); query(mid+1, r, i<<1|1); } } } int main() { char ch; int a,b,c; int L,T,O; while(~scanf("%d%d%d",&L,&T,&O)) { build(1,L,1); while(O--) { getchar(); scanf("%c",&ch); if(ch=='C') {scanf("%d %d %d",&a,&b,&c); update(a,b,c,1);} int ans=0; if(ch=='P') { memset(sum,0,sizeof(sum)); scanf("%d%d",&a,&b); query(a,b,1); for(int i=1;i<=T;i++) { if(sum[i])ans++; } printf("%d\n",ans); } } } return 0; }