首页 > 代码库 > POJ 2777 状压线段树

POJ 2777 状压线段树

2024-08-04 20:58:30   221人阅读

Count Color
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 36586 Accepted: 11041

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

2 2 4C 1 1 2P 1 2C 2 2 2P 1 2

Sample Output

21


题目意思：
有n段木板，每段木板初始化颜色1，m个操作：C l r val 即把第l段到第r段木板全染成颜色val；P l r 输出第l段到第r段木板不同颜色的数目。

思路：
颜色最多为30，状压颜色就行了，此段有该颜色，那么这一位为1，否则为0。线段树每个结点有一个flag标志，true的话就可以向下更新，false的话不能向下更新------区间更新老套路了。


代码：
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8  9 #define N 10000510 #define ll root<<111 #define rr root<<1|112 #define mid (a[root].l+a[root].r)/213 int max(int x,int y){return x>y?x:y;}14 int min(int x,int y){return x<y?x:y;}15 16 struct node{17     int l, r, val;         //val即为颜色状态18     bool flag;19 }a[N*4];20 21 int n, color, m;22 23 void build(int l, int r, int root){24     a[root].l=l;25     a[root].r=r;26     a[root].val=2;             //这里错了一次，初始化颜色为1，那么状态即为1<<1为227     a[root].flag=false;28     if(l==r) return;29     build(l,mid,ll);30     build(mid+1,r,rr);31 }32 33 void change(int l, int r, int val, int root){34     if(a[root].l==l&&a[root].r==r){35         a[root].val=1<<val;36         a[root].flag=true;37         return;38     }39     if(a[root].flag){             //若为true，且查询的段在此段里面，那么就向下更新，flag变成false40         a[root].flag=false;41         if(a[root].l!=a[root].r){42             a[ll].val=a[rr].val=a[root].val;43             a[ll].flag=a[rr].flag=true;44         }45     }46     if(l>mid) change(l,r,val,rr);47     else if(r<=mid) change(l,r,val,ll);48     else{49         change(l,mid,val,ll);50         change(mid+1,r,val,rr);51     }52     a[root].val=a[ll].val|a[rr].val;              // up53 }54 55 int find(int l,int r,int root){56     if(a[root].l==l&&a[root].r==r) return a[root].val;57     if(a[root].flag){58         a[root].flag=false;59         if(a[root].l!=a[root].r){60             a[ll].val=a[rr].val=a[root].val;61             a[ll].flag=a[rr].flag=true;62         }63     }64     if(l>mid) return find(l,r,rr);65     else if(r<=mid) return find(l,r,ll);66     else{67         return find(l,mid,ll)|find(mid+1,r,rr);68     }69     a[root].val=a[ll].val|a[rr].val;70 }71 72 main()73 {74     int i, j, k;75     char s[10];76     int x, y, z;77     while(scanf("%d %d %d",&n,&color,&m)==3){78         build(1,n,1);79         while(m--){80             scanf("%s",s);81             if(strcmp(s,"C")==0){82                 scanf("%d %d %d",&x,&y,&z);83                 change(min(x,y),max(x,y),z,1);84             }85             else if(strcmp(s,"P")==0){86                 scanf("%d %d",&x,&y);87                 int num=find(min(x,y),max(x,y),1), ans=0;88                 89                 for(i=0;i<=color;i++) {90                     if((1<<i)&num) ans++;         91                 }92                 printf("%d\n",ans);93             }94         }95         96     }97 }

 

POJ 2777 状压线段树


联系
我们