线段树+状压

在线段树上维护一个值表示这个区间的颜色，具体地讲，我们将这个区间的颜色进行状压，第1种颜色对应状压后的第1位，以此类推。这样我们维护的这个数就是状压之后的数，在合并区间时将两个数按位或即可，区间取值直接覆盖即可，最后我们统计答案时只需统计这个数有多少个1即可。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 typedef long long ll; 7 int sum[100010<<2],tag[100010<<2],n,m,t; 8 inline int read() { 9     int ret=0;10     int op=1;11     char c=getchar();12     while(c<'0'||c>'9') {
    if(c=='-') op=-1; c=getchar();}13     while(c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();14     return ret*op;15 }16 inline void pushup(int now) {17     sum[now]=sum[now<<1]|sum[now<<1|1];18 }19 inline void pushdown(int now) {20     if(tag[now]) {21         tag[now<<1]=tag[now<<1|1]=tag[now];22         sum[now<<1]=sum[now<<1|1]=1<
          
           >1;32     build(now<<1,l,mid);33     build(now<<1|1,mid+1,r);34     pushup(now);35 }36 void updata(int now,int l,int r,int x,int y,int val) {37     if(x<=l&&r<=y) {38         tag[now]=val;39         sum[now]=1<
           
            >1;44 if(x<=mid) updata(now<<1,l,mid,x,y,val);45 if(y>mid) updata(now<<1|1,mid+1,r,x,y,val);46 pushup(now);47 }48 int query(int now,int l,int r,int x,int y) {49 if(x<=l&&r<=y) return sum[now];50 pushdown(now);51 int mid=l+r>>1;52 int ret=0;53 if(x<=mid) ret|=query(now<<1,l,mid,x,y);54 if(y>mid) ret|=query(now<<1|1,mid+1,r,x,y);55 return ret;56 }57 int main() {58 n=read(); m=read(); t=read();59 build(1,1,n);60 while(t--) {61 int x,y,z;62 char op;63 cin>>op>>x>>y;64 if(op=='C') {65 cin>>z;66 if(x>y) swap(x,y);67 updata(1,1,n,x,y,z);68 }69 else {70 if(x>y) swap(x,y);71 int ret=query(1,1,n,x,y);72 int ans=0;73 for(int i=1;i<=m;i++)74 if(ret&(1<