描述：
给你一个长为L的木板，L是一个整数，我们把它分成L格1、2…，L，我们现在对在这块木板上涂色，每个小格只能涂一种颜色。
现在有两种操作
1：”C A B C”，把在[A,B]之间全部涂成颜色C，原先的颜色会被覆盖。
2：”P A B”，输出[A,B]内不同的颜色数。 颜色用数字表示，初始时整块木板涂为颜色1
输入：
每个文件一组测试数据，
第一行为”L T O”
L： (1 <= L <= 100000) 表示木板长度
T：(1 <= T <= 30) 表示所使用的颜色总数，颜色为[1,T]
O：(1 <= O <= 100000) 表示操作数
接下来有O行，每行包括"C A B C" 或者 "P A B" （A可能大于B，此时区间为[B,A]）。
1 <= A,B <= L
输出：
对于每个P操作输出一行结果。
样例输入：
2 2 4 C 1 1 2 P 1 2 C 2 2 2 P 1 2
样例输出：
2 1
典型的线段树。一种比较常见的思路是用位压缩记录每一条线段的颜色，返回的值把所有区间求一次或（并集）。但是我没有这么做，我使用的是每个节点只记录它是否是混色，如果是混色那就继续往下查询，直到找到一条纯色线段后再把颜色总数加1。这样要好写一些，但是很明显是要慢一些，比较适合我这种对位运算不敏感的人。还有一点就是本题只有30种颜色，所以这种方法能够过，如果每个点都颜色不同，那我这种方法就惨了，还是老老实实写位压缩吧。
PS：这种方法绝对能过！！！以图为证：
上代码，我相信注释还是很详细的。
View Code 1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 5 #define lson l, m, rt<<1 6 #define rson m+1, r, rt<<1|1 7 8 const int MAXN = 111111; 9 const int MIX = -1003;//混色标记，用于表示一个节点包含多种颜色。 10 const int MAXC = 33; 11 12 int col[MAXN<<2|1], L, T, O; 13 bool coltab[MAXC]; 14 //col表示每个节点上的颜色，或者是混色标记MIX 15 16 void build(int l, int r, int rt) 17 { 18 col[rt] = 1;//建树操作，把所有节点的颜色赋为1. 19 if (l == r) return ; 20 21 int m = (l+r)>>1; 22 build(lson); 23 build(rson); 24 } 25 26 void update(int color, int L, int R, int l, int r, int rt)//更新操作 27 { 28 if (col[rt] != color)//如果颜色与当前节点的颜色不一致，则进行涂色操作。 29 { 30 if (L<=l&&r<=R)//如果当前节点的区间被涂色区间完全覆盖，就直接把它标记为纯色。 31 { 32 col[rt] = color; 33 return ; 34 } 35 36 if (col[rt] != MIX)//如果区间未被完全覆盖，把该节点标记为混色，并把颜色标记下传。 37 { 38 col[rt<<1] = col[rt]; 39 col[rt<<1|1] = col[rt]; 40 col[rt] = MIX; 41 } 42 43 int m = (l+r)>>1;//和普通线段树一样的传递标记。 44 if (L <= m) update(color, L, R, lson); 45 if (m < R) update(color, L, R, rson); 46 } 47 } 48 49 void count(int L, int R, int l, int r, int rt) 50 { 51 if (col[rt] != MIX)//如果找到当前线段是纯色，就把颜色数加1，并且无需再往下查找。 52 { 53 coltab[col[rt]] = 1; 54 return ; 55 } 56 57 int m = (l+r)>>1;//如果是混色，就继续向下查找。 58 if (L <= m) count(L, R, lson); 59 if (m < R) count(L, R, rson); 60 } 61 62 int main() 63 { 64 freopen("colour.in", "r", stdin); 65 freopen("colour.out", "w", stdout); 66 67 scanf("%d%d%d", &L, &T, &O); 68 69 build(1, L, 1); 70 71 while (O--) 72 { 73 char com[2];int a, b, c; 74 scanf("%s", com); 75 switch (com[0]) 76 { 77 case 'C': 78 { 79 scanf("%d%d%d", &a, &b, &c); 80 if (a>b) a^=b^=a^=b; 81 82 update(c, a, b, 1, L, 1); 83 break; 84 } 85 case 'P': 86 { 87 scanf("%d%d", &a, &b); 88 if (a>b) a^=b^=a^=b; 89 90 for (int j=1; j<=T; j++) coltab[j] = 0; 91 count(a, b, 1, L, 1); 92 93 int res = 0;//更新和统计，我这里写复杂了，如果只是询问数目没有这么麻烦。 94 for (int j=1; j<=T; j++) res += coltab[j]; 95 printf("%d\n", res); 96 break; 97 } 98 } 99 } 100 101 return 0; 102 }转载于:https://www.cnblogs.com/stickjitb/archive/2012/07/12/2588034.html
相关资源：各显卡算力对照表！