Count Colour_poj2777(线段树+位)

POJ 2777 Count Color (线段树)

Count Color

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 29895		Accepted: 8919

Description

Chosen Problem Solving and Program design as an optional course, you are required to solve all kinds of problems. Here, we get a new problem.

There is a very long board with length L centimeter, L is a positive integer, so we can evenly divide the board into L segments, and they are labeled by 1, 2, ... L from left to right, each is 1 centimeter long. Now we have to color the board - one segment with only one color. We can do following two operations on the board:

1. "C A B C" Color the board from segment A to segment B with color C.
2. "P A B" Output the number of different colors painted between segment A and segment B (including).

In our daily life, we have very few words to describe a color (red, green, blue, yellow…), so you may assume that the total number of different colors T is very small. To make it simple, we express the names of colors as color 1, color 2, ... color T. At the beginning, the board was painted in color 1. Now the rest of problem is left to your.

Input

First line of input contains L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000). Here O denotes the number of operations. Following O lines, each contains "C A B C" or "P A B" (here A, B, C are integers, and A may be larger than B) as an operation defined previously.

Output

Ouput results of the output operation in order, each line contains a number.

Sample Input

Sample Output

2
1

Source

POJ Monthly--2006.03.26,dodo

分析一个有n（n<100000）个单位的画板，但颜色只有30种，我没有马上想到位运算，但后来和一个宋词学仙交流的时候她告诉了我可以用位，不过她也是先用的布尔数组来判断的，可能会TLE

这个线段树的提就比较标准了，我先前写的时候一直没有想到好的延时更新的方法，最后慢慢想了一下午和一晚上终于弄对了

AC代码

  1 #include<iostream>
  2 #include<cstdio>
  3 #define maxx 100005
  4 #define L(u) (u<<1)
  5 #define R(u) (u<<1|1)
  6 using namespace std;
  7 int n,t,Q;
  8 int result,ans;
  9 struct xx{
 10     int ls,rs;
 11     int clr;
 12     int sta;
 13 }node[maxx<<2];
 14 void pushup(int u)
 15 {
 16     node[u].clr=node[R(u)].clr|node[L(u)].clr;
 17 }
 18 void pushdown(int u)
 19 {
 20     node[u].sta=0;
 21     node[R(u)].clr=node[u].clr;
 22     node[L(u)].clr=node[u].clr;
 23     if(node[L(u)].ls!=node[L(u)].rs)
 24     node[L(u)].sta=1;
 25     if(node[R(u)].ls!=node[R(u)].rs)
 26     node[R(u)].sta=1;
 27 }
 28 void Build(int u,int l,int r)
 29 {
 30     node[u].ls=l;
 31     node[u].rs=r;
 32     node[u].clr=2;
 33     if(l==r)
 34         return;
 35     int mid=(l+r)>>1;
 36     Build(L(u),l,mid);
 37     Build(R(u),mid+1,r);
 38 }
 39 void Updata(int u,int l,int r,int c)
 40 {
 41     if(l==node[u].ls&&node[u].rs==r)
 42     {
 43         node[u].clr=(1<<c);
 44         if(node[u].ls!=node[u].rs)node[u].sta=1;
 45         return;
 46     }
 47     if(node[u].sta)pushdown(u);        //下传是必要的 
 48     int mid=(node[u].ls+node[u].rs)>>1;
 49     if(r<=mid)  Updata(L(u),l,r,c);
 50     else if(l>mid)  Updata(R(u),l,r,c);
 51     else{
 52         Updata(L(u),l,mid,c);
 53         Updata(R(u),mid+1,r,c);
 54     }
 55     pushup(u);
 56 }
 57 void Qurey(int u,int l,int r)
 58 {
 59     if(l==node[u].ls&&node[u].rs==r)
 60     {
 61         result=result|node[u].clr;
 62         return;
 63     }
 64     if(node[u].sta)pushdown(u);        //下传是必要的
 65     int mid=(node[u].ls+node[u].rs)>>1;
 66     if(r<=mid) Qurey(L(u),l,r);
 67     else if(l>mid) Qurey(R(u),l,r);
 68     else{
 69         Qurey(L(u),l,mid);
 70         Qurey(R(u),mid+1,r);
 71     }
 72 }
 73 int main()
 74 {
 75     while(~scanf("%d %d %d
",&n,&t,&Q))
 76     {
 77         Build(1,1,n);
 78         while(Q--)
 79         {
 80             char x;
 81             int a,b,c;
 82             scanf("%c",&x);
 83             if(x=='P')
 84             {
 85                 result=0,ans=0;
 86                 scanf("%d %d
",&a,&b);
 87                 if(a>b)
 88                 {a=a+b;b=a-b;a=a-b;}
 89                 Qurey(1,a,b);
 90                 while(result)
 91                 {
 92                     result>>=1;
 93                     if(1&result)ans++;
 94                 }
 95                 cout<<ans<<endl;
 96             }
 97             else
 98             {
 99                 scanf("%d %d %d
",&a,&b,&c);
100                 if(a>b)
101                 {a=a+b;b=a-b;a=a-b;}//注意查询的区间可能左大于右数据怪怪的 
102                 Updata(1,a,b,c);
103             }
104         }
105     }
106     return 0;
107 }