$$Count Color$$

Time Limit: 1000MS

Memory Limit: 65536K

Total Submissions: 50865

Accepted: 15346

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 2

Sample Output

2

1

Source

POJ Monthly--2006.03.26,dodo

Submit

题解

题目大意：我们需要设计一个程序,支持两种操作

• 修改:把区间\([l,r]\)内的颜色全部换成\(Q\)
• 询问:区间\([l,r]\)内有多少种不同的颜色
• 其中颜色数T\(<=30\)

本来博主蒟蒻看错题了,以为是SDOI2011染色那样询问区间内有多少个颜色段,然后迅速码完交了一发,结果WA,然后还以为是自己打错了,一直在调,后来发现是自己理解错题意了,重新打了一次,看到了颜色\(T<=30\),这对int类型状态压缩是完全没有问题的,然后就是乱打了,我们把颜色i表示为\(1<<(i-1)\)代表第i中颜色,这样在统计颜色数的时候把每一位拆开,看这一位是否是1

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define in(i) (i=read())
#define ll(i) (i<<1)
#define rr(i) (i<<1|1)
#define mid (l+r>>1)
using namespace std;
int read() {
    int ans=0,f=1; char i=getchar();
    while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
    while(i>='0' && i<='9') {ans=(ans<<1)+(ans<<3)+i-'0'; i=getchar();}
    return ans*f;
}
int n,m,T,ans;
int sum[400010],lazy[400010];
inline void pushup(int node) {
    sum[node]=sum[ll(node)]|sum[rr(node)];
}
inline void pushdown(int node) {
    lazy[ll(node)]=lazy[node];
    lazy[rr(node)]=lazy[node];
    sum[ll(node)]=sum[rr(node)]=lazy[node];
    lazy[node]=0;
}
void build(int node,int l,int r) {
    if(l==r) {
        sum[node]=1;
        return;
    }
    build(ll(node),l,mid);
    build(rr(node),mid+1,r);
    pushup(node);
}
void update(int node,int l,int r,int left,int right,int k) {
    if(l>right || r<left) return;
    if(left<=l && r<=right) {
        lazy[node]=1<<k-1;
        sum[node]=1<<k-1;
        return;
    }
    if(lazy[node]) pushdown(node);
    update(ll(node),l,mid,left,right,k);
    update(rr(node),mid+1,r,left,right,k);
    pushup(node);
}
inline int work(int x) {
    int ans=0;
    while(x) {
        if(x&1) ans++;
        x>>=1;
    }
    return ans;
}
void check(int node,int l,int r,int left,int right) {
    if(l>right || r<left) return;
    if(left<=l && r<=right) {
        ans|=sum[node];
        return;
    }
    if(lazy[node]) pushdown(node);
    check(ll(node),l,mid,left,right);
    check(rr(node),mid+1,r,left,right);
}
int main()
{
    while(scanf("%d%d%d",&n,&T,&m)!=EOF) {
        memset(lazy,0,sizeof(lazy));
        int x,y,k; build(1,1,n);
        for(int i=1;i<=m;i++) {
            char op[10]; scanf("%s",op);
            if(op[0]=='C') {
                in(x); in(y); in(k);
                if(x>y) swap(x,y);
                update(1,1,n,x,y,k);
            }
            else {
                ans=0; in(x); in(y);
                if(x>y) swap(x,y);
                check(1,1,n,x,y); ans=work(ans);
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

博主蒟蒻,随意转载.但必须附上原文链接

http://www.cnblogs.com/real-l/