首页 > > 程序设计 > C/C++ >

POJ 27777 count color （线段树——带lazy标志…

2018-06-17 21:43:47来源：未知阅读 ()


  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 }