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

/*
之前的思想是用回溯的方式进行颜色的更新的！如果用回溯的方法的话，就是将每一个节点的颜色都要更新
通过子节点的颜色情况来判断父节点的颜色情况 ！这就是TLE的原因！

后来想一想没有必要 ！加入[a, b] 区间有p管辖，那么tree[p]的颜色值就是[a, b]所有点的颜色值！
如果[a,b]的子区间[c,d]没被跟新，那么tree[p]也是[c,d]的值！
否则，在更新[c,d]区间的时候，一定会经过 p 点！然后由上到下更新p<<1 和 p<<1|1 的值!
当找到[c,d]区间所对应的p‘时，并更新p’的值！、

之前的剪枝是点返回， 后面的是线段返回，当然更快！ 
*/ 
#include<string> 
#include<iostream> 
#include<algorithm>
#include<cstring>
#include<cstdio>
#define M 100005 
using namespace std;


int tree[4*M];

int color[32];
int L, T, O;


void buildT(int ld, int rd, int p){
    if(ld<=rd){
        tree[p]=1;
        if(ld==rd)
           return ;
         int mid = (ld+rd)/2;
         buildT(ld, mid, p<<1);
         buildT(mid+1, rd, p<<1|1);
    }
}



void updateT(int ld, int rd, int a, int b, int p, int k){
    if(tree[p] == k) return ;//如果当前更新的颜色和 之前p所管辖的区间的颜色相同，则返回 
    
    if(ld==a && rd==b){//p所管辖的区间的点的颜色全部是k！如果其子区间的颜色被更改，那么 
        tree[p]=k;     //在更新子区间的时候一定会经过 p点，让后通过p更新 p<<1 和 p<<1|1 子区间的颜色！ 
        return ;
    }
    
    if(tree[p]!=-1){//也就是在经过父节点时更新子节点的颜色状态，也就是[a,b]包含在 p点所管辖的区间内 
       tree[p<<1] = tree[p<<1|1] = tree[p];
       tree[p]=-1;
    }
    if(ld<rd){
       int mid = (ld+rd)/2;
       if(mid<a)
         updateT(mid+1, rd, a, b, p<<1|1, k);
       else if(mid>=b)
         updateT(ld, mid, a, b, p<<1, k);
       else{
          updateT(ld, mid, a, mid, p<<1, k);
          updateT(mid+1, rd, mid+1, b, p<<1|1, k);
       }
    }
}

void queryT(int ld, int rd, int a, int b, int p){
   if(ld>rd) return ;
   if(tree[p]!=-1){
         color[tree[p]]=1; 
   }
   else{
       int mid = (ld+rd)/2;
       if(mid<a)
         queryT(mid+1, rd, a, b, p<<1|1);
       else if(mid>=b)
         queryT(ld, mid, a, b, p<<1);
       else{
          queryT(ld, mid, a, mid, p<<1);
          queryT(mid+1, rd, mid+1, b, p<<1|1);
       }
   }
}

int main(){
   
   while(scanf("%d%d%d", &L, &T, &O)!=EOF){
      buildT(1, L, 1);
      while(O--){
         char ch[2];
         int a, b, c;
         scanf("%s", ch);
         if(ch[0]=='C'){
             scanf("%d%d%d", &a, &b, &c);
             if(a>b){
               a^=b;
               b^=a;
               a^=b; 
            }  
             updateT(1, L, a, b, 1, c);
         }         
         else{
            scanf("%d%d", &a, &b);
            if(a>b){
               a^=b;
               b^=a;
               a^=b; 
            } 
            memset(color, 0, sizeof(color));
            queryT(1, L, a, b, 1); 
            int cnt=0;
            for(int i=1; i<=T; ++i)
               if(color[i]) ++cnt;
            printf("%d\n", cnt);
         }
      }
   }
   return 0;
}