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 4 C 1 1 2 P 1 2 C 2 2 2 P 1 2Sample Output
2 1题意：有一个长度为 n 的区间，最多共有30种颜色，然后有 m 次操作，每一次操作是将区间 [a,b] 颜色染为 c ，或者查询 [a,b] 的颜色有多少种
思路：首先就是染色的操作，这个很简单。我这里解释一下怎么找不同的颜色数量，因为最多只有30种颜色，所以我们可以用二进制的一个位为1来代表这个颜色，那么30种颜色分别对应的值是 1,2,4,8,16 .... 每一次update的时候 直接用 或运算，就可以达到去重，统计的目的。 最后只需要将query的值逐个按位分解，该位是1的话，就颜色数 ++
代码：
#include<set> #include<cstdio> #include<cstring> #include<iostream> #define debug(x) cout << "[" << #x <<": " << (x) <<"]"<< endl #define pii pair<int,int> #define clr(a,b) memset((a),b,sizeof(a)) #define rep(i,a,b) for(int i = a;i < b;i ++) #define pb push_back #define MP make_pair #define LL long long #define ull unsigned LL #define ls i << 1 #define rs (i << 1) + 1 #define INT(t) int t; scanf("%d",&t) using namespace std; const int maxn = 1e5 + 10; int type[maxn << 2]; int Size[maxn << 2],model[40]; void pushdown(int i){ if(type[i]){ type[i << 1] = type[i << 1 | 1] = type[i]; Size[i << 1] = Size[i << 1 | 1] = Size[i]; type[i] = 0; } } void update(int l,int r,int ul,int ur,int i,int val){ if(ul <= l && r <= ur){ type[i] = val; Size[i] = model[val]; return ; } pushdown(i); int mid = (l + r) >> 1; if(ul <= mid) update(l,mid,ul,ur,i << 1,val); if(ur > mid) update(mid + 1,r,ul,ur,i << 1 | 1,val); Size[i] = (Size[i << 1] | Size[i << 1 | 1]); } int query(int l,int r,int ql,int qr,int i){ if(ql <= l && r <= qr){ return Size[i]; } pushdown(i); int ans = 0,mid = (l + r) >> 1; if(ql <= mid) ans |= query(l,mid,ql,qr,i << 1); if(qr > mid) ans |= query(mid + 1,r,ql,qr,i << 1 | 1); return ans; } int main() { int l,t,o; model[1] = 1; for(int i = 2;i <= 30;++ i) model[i] = model[i - 1] * 2; while(~scanf("%d%d%d",&l,&t,&o)){ clr(type,0); clr(Size,0); update(1,l,1,l,1,1); while(o --){ char ch; scanf(" %c",&ch); if(ch == 'C'){ int a,b,c; scanf("%d%d%d",&a,&b,&c); if(a > b) swap(a,b); update(1,l,a,b,1,c); } else { int a,b; scanf("%d%d",&a,&b); if(a > b) swap(a,b); int tmp = query(1,l,a,b,1),ans = 0; while(tmp){ if(tmp & 1) ++ ans; tmp >>= 1; } printf("%d\n",ans); } } } return 0; }
