（此题与POJ2777重题）
为了加深对线段树的记忆，然后开始搞这道题。
TM的WA了一下午就是发现x可能大于y（然而题目里说的还很清楚，我TM没看见）
这道题只需要在线段树的板子上改一些地方就可以了：
1.存储时不是存储颜色，而是将它状压成一个整数（如序号为3的颜色存为1<<3=8）
2.回溯时不是取和相加，而是直接按位或（|），原理等下讲
3.最后的查询完毕的值统计一下二进制下有多少个1就是ans
最后讲一下为什么要|
假如3种颜色 2,3,3，在树上记为4,8,8，它们对应的二进制就是（100,1000,1000）
有没有发现，每个数的二进制下都只有一位上有1，而且不同颜色的数1的位置不同
因此在|的时候，只要这一位上有1，那么就一定有这种颜色
线段树就是板子，套一套就好了
CODE
#include<cstdio> #include<iostream> using namespace std; const int N=100005; int tree[N*4],add[N*4],l,t,o,x,y,z; char ch; inline void read(int &x) { x=0; char ch=getchar(); int flag=1; while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=getchar(); } while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); x*=flag; } inline void write(int x) { if (x/10) write(x/10); putchar(x%10+'0'); } inline void up(int root) { tree[root]=tree[root*2]|tree[root*2+1]; } inline void down(int root) { if (add[root]) { tree[root*2]=add[root]; tree[root*2+1]=add[root]; add[root*2]=add[root]; add[root*2+1]=add[root]; add[root]=0; } } inline void build(int root,int l,int r) { if (l==r) { tree[root]=2; return; } int mid=l+r>>1; build(root*2,l,mid); build(root*2+1,mid+1,r); up(root); } inline void change(int root,int l,int r,int beg,int end,int col) { if (l>=beg&&r<=end) { tree[root]=1<<col; add[root]=1<<col; return; } down(root); int mid=l+r>>1; if (beg<=mid) change(root*2,l,mid,beg,end,col); if (end>mid) change(root*2+1,mid+1,r,beg,end,col); up(root); } inline int query(int root,int l,int r,int beg,int end) { if (l>=beg&&r<=end) return tree[root]; down(root); int mid=l+r>>1,res=0; if (beg<=mid) res|=query(root*2,l,mid,beg,end); if (end>mid) res|=query(root*2+1,mid+1,r,beg,end); up(root); return res; } inline int calc(int x) { int res=0; while (x) { if (x%2==1) res++; x>>=1; } return res; } int main() { read(l); read(t); read(o); build(1,1,l); while (o--) { cin>>ch; if (ch=='C') { read(x); read(y); read(z); if (x>y) swap(x,y); change(1,1,l,x,y,z); }else { read(x); read(y); if (x>y) swap(x,y); write(calc(query(1,1,l,x,y))); putchar(' '); } } return 0; }