查询和修改给定区间的颜色种类，将一个区间的颜色种类k用二进制数2^k表达，位运算求或即可得出任意区间的不同颜色种类。
查询量巨大，建议按线段更新，不要每次都更新到树叶。
我也不明白我的程序怎么那么慢。。。 求xxms做法。
1
/**//*Source Code
2
3Problem: 2777 User: _mTy
4Memory: 4024K Time: 329MS
5Language: C++ Result: Accepted
6
7
*/
8
#include<stdio.h>
9#include<string.h>
10#define MAXV 666666
11#define swap(a,b) a^=b^=a^=b
12
13typedef unsigned long _UL;
14typedef _UL ele_t;
15ele_t data[MAXV];
16int B[MAXV],E[MAXV],LSON[MAXV],RSON[MAXV],C[MAXV];
17int cnt;
18bool fill[MAXV];
19// B[] E[] 存放 [a,b]左界 右界
20// C[] 覆盖当前区间的线段数
21// LSON,RSON 点v的左右儿子的数组下标
22// fill[] 指示特定区间是否仅被一种颜色填充
23
24void ini(int u,int v)
{
25 int i;
26 ++cnt; i = cnt; B[i] = u; E[i] = v;
27
if( v - u >= 1 ){
28 LSON[i] = cnt+1; ini(u,(u+v)/2);
29 RSON[i] = cnt+1; ini((u+v)/2+1,v);
30
}
31}
32
33void insert(int u,int v,int r,ele_t ele){ // 将区间[u,v]信息 data 插入以 r 为根的线段树
34 if( u <= B[r] && v >= E[r] ){
35 data[r] = 1UL<<ele-1;
36 fill[r] = 1;
37 }else{
38 if( fill[r] == 1 ){ data[LSON[r]] = data[RSON[r]] = data[r]; fill[LSON[r]] = fill[RSON[r]] = 1; }
39
40 if( u <= (B[r]+E[r])/2 ) insert(u,v,LSON[r],ele);
41 if( v >= (B[r]+E[r])/2+1 ) insert(u,v,RSON[r],ele);
42
43 // updata [u,v]
44 data[r] = data[LSON[r]] | data[RSON[r]];
45 fill[r] = 0;
46 }
47}
48
49_UL out(int u,int v,int r){
50 int data_1 = 0,data_2 = 0;
51 if( fill[r] == 1 || u <= B[r] && v >= E[r] ) return data[r];
52 else{
53 if( u <= (B[r]+E[r])/2 ) data_1 = out(u,v,LSON[r]);
54 if( v >= (B[r]+E[r])/2+1 ) data_2 = out(u,v,RSON[r]);
55 return data_1 | data_2;
56 }
57}
58
59int main(){
60 int i,j,l,t,o,u,v,cc,res;
61 _UL val;
62 char chr;
63 while(scanf("%d%d%d",&l,&t,&o)!=EOF){
64 getchar();
65
66 data[1] = 1UL;
67 cnt = 0; ini(1,l);
68 memset(fill,0,sizeof(bool)*(cnt+1)); fill[1] = 1; // 初始区间 [u,v] 被1颜色填充
69
70 for(i=0;i<o;i++){
71 scanf("%c%d%d",&chr,&u,&v);
72 if( u>v ) swap(u,v);
73 if( chr == 'C' ){
74 scanf("%d",&cc);
75 getchar();
76 insert(u,v,1,cc);
77 }else{
78 getchar();
79 val = out(u,v,1);
80 res = 0;
81 for(j=0;j<t;j++) if( val & 1UL<< j ) ++res;
82 printf("%d\n",res);
83 }
84 }
85 }
86 return 0;
87}