POJ 27777 count color （線段樹——帶lazy標誌）

  1 //作為一個蒟蒻，這麼高深的代碼當然不可能是我打的，我只是大佬的搬運工
  2 //（不過有一些註解是本人補上去，如果有什麼問題，望海涵） 
  3 
  4 
  5 
  6 /* 
  7   功能Function Description:     POJ 2777 線段樹
  8   開發環境Environment:          DEV C++ 4.9.9.1
  9   題意：
 10      給定一個長度為N(N <= 100000)的數列Si，緊接著Q(Q <= 100000)條操作，操作
 11   形式有兩種：
 12   1. "C A B C" 將A到B的數都染成C這種顏色。 
 13   2. "P A B" 輸出A和B之間不同顏色的數目。
 14 
 15  解法：-------轉線段樹（染色問題）
 16  
 17   思路：
 18       一看到數據量就可以首先確定是線段樹了，經典的區間染色問題，涉及到區間的
 19   更新和詢問，和pku 3468 類似，巧妙運用lazy思想。就是每次更新區間段的時候延遲
 20   更新，只是在完全覆蓋的區間打上一個lazy標記。這題的詢問是求區間段中不同顏色的
 21   數量，因為顏色數不多只有30種，可以巧妙運用二進位位運算，用一個int就可以表示
 22   當前區間段的顏色情況。比如1001表示有兩種顏色，如果左子樹的當前顏色情況是101 ，
 23   而右子樹的顏色情況是011，那麼父親的顏色情況就是兩者的位或，這樣就可以避免
 24  掉重覆的情況。
 25     
 26     再來談談lazy思想。做了這麼多的線段樹，應該總結一下，lazy是一個很經典的思
 27   想。所謂lazy，就是懶惰，每次不想做太多，只要插入的區間完全覆蓋了當前結點所管
 28  理的區間就不再往下做了，在當前結點上打上一個lazy標記，然後直接返回。下次如果
 29  遇到當前結點有lazy標記的話，直接傳遞給兩個兒子，自己的標記清空。這樣做肯定是
 30  正確的。我們以染色為例，可以這樣想，如果當前結點和它的子孫都有lazy標記的話，
 31  必定是子孫的先標記，因為如果是自己先標記，那麼在訪問子孫的時候，必定會將自己
 32  的標記下傳給兒子，而自己的標記必定會清空，那麼lazy標記也就不存在了。所以可以
 33  肯定，當前的lazy標記必定覆蓋了子孫的，所以直接下傳即可，不需要做任何判斷。當
 34   然，這是染色問題，是直接賦值的，如果像pku 3468那樣，每次是區間加和，則傳遞標
 35   記的時候不能簡單的賦值，必須累加，這是顯而易見的。 */
 36 
 37 #include <iostream>
 38 #include <cstdio>
 39 #include <cstring>
 40 using namespace std; 
 41 struct node
 42 {
 43     int lc,rc; 
 44     int state;  //用二進位中的每一位中的1的個數來標記顏色個數 
 45     int id;    //標記狀態看是否被完全覆蓋 
 46 }tree[300010];
 47 
 48 void build (int s,int t,int T)
 49 {
 50     int mid;
 51     tree[T].lc=s;//數組起始位置 
 52     tree[T].rc=t;//數組結束位置 
 53     if(s==t) //葉子結點 
 54       return ;
 55     mid=(s+t)>>1;//位運算，等價於 mid=(s+t)/2; 
 56     build(s,mid,T<<1);//遞歸構造左子樹 
 57     build(mid+1,t,(T<<1)|1);//遞歸構造右子樹 ,位運算，等價於 build(mid+1,t,(T*2)+1)
 58      
 59 }
 60 void insert(int s,int t,int T,int value)  //從s到t塗上顏色value，從T節點開始查找 
 61 {
 62     int mid;
 63     if(tree[T].lc==s &&tree[T].rc==t) //說明塗色範圍正好完全覆蓋T所包含的區域，直接更新顏色信息，下邊的節點不用管
 64     {
 65        tree[T].id=1; //標記為完全覆蓋
 66        tree[t].state=1<<(value-1); //不同的顏色用二進位不同位上的1表示
 67        return ; 
 68     }
 69     if(tree[T].id) //說明T是完全覆蓋的，更新T孩子節點的信息
 70     {
 71         tree[T].id=0;//當前節點刪去標記 
 72         tree[T<<1].id=tree[(T<<1)|1].id=1;//這是連等吧？還可以有這種操作，長見識了
 73         tree[T<<1].state=tree[(T<<1)|1].state=tree[T].state;//當前節點的顏色個數傳遞給他的左、右子樹 
 74     } 
 75     mid=(tree[T].lc+tree[T].rc)>>1;
 76     
 77     if(t<=mid)   //說明塗色範圍在T節點的左子樹 
 78       insert(s,t,T<<1,value);
 79     else if(s>mid) //說明塗色範圍在T節點的右子樹 
 80       insert(s,t,(T<<1)|1,value);
 81     else//否則，塗色範圍橫跨T節點的左、右子樹 
 82     {
 83         insert(s,mid,T<<1,value);
 84         insert(mid+1,t,(T<<1)|1,value);
 85     } 
 86     tree[T].state=(tree[T<<1].state)|(tree[(T<<1)|1].state);//位運算，等同於把左右子樹顏色數相加 ，又避免了同一顏色多次累加
 87     if(tree[T<<1].id && tree[(T<<1)|1].id && tree[T<<1].state==tree[(T<<1)|1].state)
 88         tree[T].id=1; 
 89 }
 90 int qurry(int s,int t,int T) //從T節點開始查詢區間s到t的顏色個數 
 91 {
 92     int mid;
 93     if(tree[T].lc==s && tree[T].rc==t)
 94        return tree[T].state;
 95     if(tree[T].id)  //剪枝——說明T是全覆蓋的，直接返回狀態值即可
 96        return tree[T].state;
 97     mid=(tree[T].lc+tree[T].rc)>>1;
 98     if(t<=mid)
 99        return qurry(s,t,T<<1);
100     else if(s>mid)
101        return qurry(s,t,(T<<1)|1);
102     else
103        return qurry(s,mid,T<<1)|qurry(mid+1,t,(T<<1)|1); 
104 } 
105 int main()
106 {
107     int i,j,k,color,t,num,len,m;
108     char cmd[2];
109     while(scanf("%d%d%d",&len,&color,&m)!=EOF)
110     {
111         build(1,len,1);
112         tree[1].state=1;
113         tree[1].id=1;
114         while(m--)
115         {
116             scanf("%s",cmd);
117             if(cmd[0]=='C')
118             {
119                 scanf("%d%d%d",&i,&j,&k);
120                 if(i>j) //輸入的區間可能不按從大到小，需要進行交換，保證i<j 
121                 {
122                     t=i;
123                     i=j;
124                     j=t;
125                 }
126                 insert(i,j,1,k);
127             }
128             else
129             {
130                 scanf("%d%d",&i,&j);
131                 if(i>j)
132                 {
133                     t=i;
134                     i=j;
135                     j=t;
136                 }
137                 k=qurry(i,j,1);
138                 num=0;
139                 for(i=0;i<color;++i)
140                    if(k&(1<<i))
141                      ++num;
142                  printf("%d\n",num);
143             }
144         }
145     }
146     return 0;
147 }