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\n", cnt);113          }114       }115    }116    return 0;117 }