当前位置：首页 > news >正文

poj 2777 Count Color(线段树区间更新)

news 来源：原创 2024/5/14 16:04:08

题目：http://poj.org/problem?id=2777

大意：有个L长得木板, T种颜色，O个操作，分两种操作，一种是给从a到b区间染颜色c，另一种是询问区间a到b有多少种不同的颜色。

思路：线段树区间更新的题目，基本是模板题；

　　　注意：由于颜色的种类很少，所以可以用位操作来表示颜色；一个整数可以表示一段的颜色状态。

代码：

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 const int maxn=1000000;
  7 int tree[maxn*4];//存储区间内有多少种颜色
  8 int lz[maxn*4];//延迟标记数组
  9 int color;
 10 void push(int w)
 11 {
 12     tree[w]=tree[w<<1]|tree[w<<1|1];
 13 }
 14 void build(int l,int r,int w)
 15 {
 16     if(l==r)
 17     {
 18         tree[w]=1;
 19         return ;
 20     }
 21     int m=(l+r)>>1;
 22     build(l,m,w<<1);
 23     build(m+1,r,w<<1|1);
 24     push(w);
 25 }
 26 void update(int L,int R,int x,int l,int r,int w)
 27 {
 28     if(L<=l&&R>=r)
 29     {
 30         lz[w]=w;//标记延迟
 31         tree[w]=1<<(x-1);
 32         return ;
 33     }
 34     if(lz[w]!=0)//消除延迟标记
 35     {
 36         lz[w*2]=lz[w*2+1]=lz[w];
 37         tree[w<<1]=tree[w<<1|1]=tree[w];
 38         lz[w]=0;
 39     }
 40     int m=(l+r)>>1;
 41     if(L>m)
 42         update(L,R,x,m+1,r,w<<1|1);
 43     else if(R<=m)
 44         update(L,R,x,l,m,w<<1);
 45     else
 46     {
 47         update(L,m,x,l,m,w<<1);
 48         update(m+1,R,x,m+1,r,w<<1|1);
 49     }
 50     push(w);//更新
 51 }
 52 void query(int L,int R,int l,int r,int w)
 53 {
 54     if((L<=l&&R>=r)||lz[w]!=0)//如果这个区间有延迟标记，则表示这个区间内是一种颜色，不需要再访问其儿子
 55     {
 56         color|=tree[w];//用位操作存储颜色
 57         return;
 58     }
 59     int m=(l+r)>>1;
 60     if(R<=m)
 61     {
 62         query(L,R,l,m,w<<1);
 63     }
 64     else if(L>m)
 65     {
 66         query(L,R,m+1,r,w<<1|1);
 67     }
 68     else
 69     {
 70         query(L,m,l,m,w<<1);
 71         query(m+1,R,m+1,r,w<<1|1);
 72     }
 73 }
 74 int main()
 75 {
 76     int L,T,O;
 77     while(scanf("%d%d%d",&L,&T,&O)!=EOF)
 78     {
 79         int i;
 80         char ch;
 81         int a,b,c;
 82         int chan;
 83         memset(lz,0,sizeof(lz));
 84         build(1,L,1);
 85         for(i=0; i<O; i++)
 86         {
 87             getchar();
 88             scanf("%c",&ch);
 89             scanf("%d%d",&a,&b);
 90             if(a>b)
 91             {
 92                 chan=a;
 93                 a=b;
 94                 b=chan;
 95             }
 96             if(ch=='C')
 97             {
 98                 scanf("%d",&c);
 99                 update(a,b,c,1,L,1);
100             }
101             else
102             {
103                 color=0;
104                 query(a,b,1,L,1);
105                 int sum=0;
106                 for(int j=0; j<T; j++)
107                 {
108                     if(color&(1<<j))//计算二进制中1的个数，代表颜色的种数
109                     {
110                         sum++;
111                     }
112                 }
113                 printf("%d\n",sum);
114             }
115         }
116     }
117     return 0;
118 }