查询和修改给定区间的颜色种类,将一个区间的颜色种类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}