poj 2777（线段树的节点更新策略）

  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 }