/* * poj2777 AC * 线段树基础 * 注意:初始状态时board已经染为了颜色1 * 看到颜色只有30种时,果断想到了用二进制数来保存颜色,一个long足够了。 * * 线段树: * 线段树的基本操作参考AHYY的线段树讲稿。 * 现在终于注意到了队结点标记的重要性,即要保持结点的一致性。 * * 一致性: * 结点的一致性要求了一个结点在更新过程中必须,染色(或者数据的更新)必须完 * 整覆盖整个结点区间,否则该结点不能提供正确的信息,而必须继续查询其左右子结 * 点,直到一个具有一致性的结点出现。 * 而具有一致性的结点,就将其做上标记,有标记的结点包含的信息就可以包含其 * 子结点的所有信息了。所以查询中,查询区间若属于一个标记结点的子集,则可返回 * 标记结点的值。 * 更新线段树过程,也是一个对标记的更新。 * 注释部分为我原始的程序,即没有考虑到标记的问题。 * * */ #include<stdio.h> #include<memory.h> #define MAX 100002 struct NODE { long color; //二进制数记录有哪些颜色 long low,high; bool mark; }tree[MAX*2]; long left[MAX*2],right[MAX*2]; long l,t,o,tot = 0; void build(long a,long b) { tree[++tot].low = a,tree[tot].high = b; if(a==b) return; long m = tot; left[m] = tot+1,build(a,(a+b)/2); right[m] = tot+1,build((a+b)/2+1,b); return; } void change(long a,long b,long c,long k) { if(a>b || tree[k].low>b || tree[k].high<a) return; if(tree[k].low==a && tree[k].high==b) { tree[k].color = c; tree[k].mark =true; return; } if(tree[k].mark) { tree[right[k]].color = tree[left[k]].color = tree[k].color; tree[right[k]].mark = tree[left[k]].mark = true; tree[k].mark = false; } /** change(a,b,c,left[k]); change(a,b,c,right[k]); if(tree[k].mark) { tree[k].mark = false; if(a>mid) { change(a,b,c,right[k]),change(mid+1,a-1,tree[k].color,right[k]),change(b+1,tree[k].high,tree[k].color,right[k]); change(tree[k].low,mid,tree[k].color,left[k]); } else if(b<=mid) { change(a,b,c,left[k]),change(tree[k].low,a-1,tree[k].color,left[k]),change(b+1,mid,tree[k].color,left[k]); change(mid+1,tree[k].high,tree[k].color,right[k]); } else { change(tree[k].low,a-1,tree[k].color,left[k]); change(a,mid,c,left[k]); change(mid+1,b,c,right[k]); change(b+1,tree[k].high,tree[k].color,right[k]); } }else **/ long mid = (tree[k].low+tree[k].high)>>1; if(a>mid) change(a,b,c,right[k]); else if(b<=mid) change(a,b,c,left[k]); else { change(a,mid,c,left[k]); change(mid+1,b,c,right[k]); } if(tree[left[k]].mark && tree[right[k]].mark && tree[left[k]].color==tree[right[k]].color) tree[k].color = tree[left[k]].color,tree[k].mark = true; return; } long quiry(long a,long b,long k) { long ans = 0; // if(a>b || tree[k].low>b || tree[k].high<a) return 0; if(a>b) return 0; if(tree[k].mark && tree[k].low<=a && tree[k].high>=b) { ans = tree[k].color; return ans; } /*else { ans = quiry(a,b,left[k])|quiry(a,b,right[k]); return ans; }*/ long mid = (tree[k].low+tree[k].high)>>1; if(a>mid) ans = quiry(a,b,right[k]); else if(b<=mid) ans = quiry(a,b,left[k]); else ans = quiry(a,mid,left[k])|quiry(mid+1,b,right[k]); return ans; } int main() { // FILE* fin; // fin = fopen("d.in","r"); scanf("%ld%ld%ld",&l,&t,&o); // fscanf(fin,"%ld%ld%ld",&l,&t,&o); memset(tree,0,sizeof(0)); memset(left,0,sizeof(left)); memset(right,0,sizeof(right)); build(1,l); tree[1].mark = true,tree[1].color = 1; for(long i=1;i<=o;i++) { char s[2]; long a,b,c,t; scanf("%s",s); // fscanf(fin,"%s",s); if(s[0]=='C') { scanf("%ld%ld%ld",&a,&b,&c); // fscanf(fin,"%ld%ld%ld",&a,&b,&c); if(a>b) t = a,a = b,b = t; change(a,b,(1<<(c-1)),1); }else { scanf("%ld%ld",&a,&b); // fscanf(fin,"%ld%ld",&a,&b); if(a>b) c = a,a = b,b = c; long ans = 0,v = quiry(a,b,1); while(v) v &= (v-1),ans++; printf("%ld\n",ans); } } }