1 /*
2 之前的思想是用回溯的方式进行颜色的更新的!如果用回溯的方法的话,就是将每一个节点的颜色都要更新
3 通过子节点的颜色情况来判断父节点的颜色情况 !这就是TLE的原因!
4
5 后来想一想没有必要 !加入[a, b] 区间有p管辖,那么tree[p]的颜色值就是[a, b]所有点的颜色值!
6 如果[a,b]的子区间[c,d]没被跟新,那么tree[p]也是[c,d]的值!
7 否则,在更新[c,d]区间的时候,一定会经过 p 点!然后由上到下更新p<<1 和 p<<1|1 的值!
8 当找到[c,d]区间所对应的p‘时,并更新p’的值!、
9
10 之前的剪枝是点返回, 后面的是线段返回,当然更快!
11 */
12 #include<string>
13 #include<iostream>
14 #include<algorithm>
15 #include<cstring>
16 #include<cstdio>
17 #define M 100005
18 using namespace std;
19
20
21 int tree[4*M];
22
23 int color[32];
24 int L, T, O;
25
26
27 void buildT(int ld, int rd, int p){
28 if(ld<=rd){
29 tree[p]=1;
30 if(ld==rd)
31 return ;
32 int mid = (ld+rd)/2;
33 buildT(ld, mid, p<<1);
34 buildT(mid+1, rd, p<<1|1);
35 }
36 }
37
38
39
40 void updateT(int ld, int rd, int a, int b, int p, int k){
41 if(tree[p] == k) return ;//如果当前更新的颜色和 之前p所管辖的区间的颜色相同,则返回
42
43 if(ld==a && rd==b){//p所管辖的区间的点的颜色全部是k!如果其子区间的颜色被更改,那么
44 tree[p]=k; //在更新子区间的时候一定会经过 p点,让后通过p更新 p<<1 和 p<<1|1 子区间的颜色!
45 return ;
46 }
47
48 if(tree[p]!=-1){//也就是在经过父节点时更新子节点的颜色状态,也就是[a,b]包含在 p点所管辖的区间内
49 tree[p<<1] = tree[p<<1|1] = tree[p];
50 tree[p]=-1;
51 }
52 if(ld<rd){
53 int mid = (ld+rd)/2;
54 if(mid<a)
55 updateT(mid+1, rd, a, b, p<<1|1, k);
56 else if(mid>=b)
57 updateT(ld, mid, a, b, p<<1, k);
58 else{
59 updateT(ld, mid, a, mid, p<<1, k);
60 updateT(mid+1, rd, mid+1, b, p<<1|1, k);
61 }
62 }
63 }
64
65 void queryT(int ld, int rd, int a, int b, int p){
66 if(ld>rd) return ;
67 if(tree[p]!=-1){
68 color[tree[p]]=1;
69 }
70 else{
71 int mid = (ld+rd)/2;
72 if(mid<a)
73 queryT(mid+1, rd, a, b, p<<1|1);
74 else if(mid>=b)
75 queryT(ld, mid, a, b, p<<1);
76 else{
77 queryT(ld, mid, a, mid, p<<1);
78 queryT(mid+1, rd, mid+1, b, p<<1|1);
79 }
80 }
81 }
82
83 int main(){
84
85 while(scanf("%d%d%d", &L, &T, &O)!=EOF){
86 buildT(1, L, 1);
87 while(O--){
88 char ch[2];
89 int a, b, c;
90 scanf("%s", ch);
91 if(ch[0]=='C'){
92 scanf("%d%d%d", &a, &b, &c);
93 if(a>b){
94 a^=b;
95 b^=a;
96 a^=b;
97 }
98 updateT(1, L, a, b, 1, c);
99 }
100 else{
101 scanf("%d%d", &a, &b);
102 if(a>b){
103 a^=b;
104 b^=a;
105 a^=b;
106 }
107 memset(color, 0, sizeof(color));
108 queryT(1, L, a, b, 1);
109 int cnt=0;
110 for(int i=1; i<=T; ++i)
111 if(color[i]) ++cnt;
112 printf("%d
", cnt);
113 }
114 }
115 }
116 return 0;
117 }