Count Color
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 55483 Accepted: 16628
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 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
Sample Output

2
1

题意：可以理解为L为多少个气球，T代表有多少种颜色，O代表操作数。C命令是区间[A,B]的气球染成C颜色，P命令是查询区间[A,B]有多少不同的颜色。
题解：一开始的时候是线段树维护大小为30的数组，明显被卡掉了。于是换了个思路，其实就是用二进制做，最大就是1<<L-1，而每一位二进制上代表存在，0代表不存在。于是就能很简单的用位运算进行实现，唯一的难点就是要想到二进制，幸好做这道题的前一天学的是状压dp。

#include<iostream>
#include<cstring>
#include<sstream>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<list>
#include<set>
#include<map>
#include<algorithm>
#define fi first
#define se second
#define MP make_pair
#define P pair<int,int>
#define PLL pair<ll,ll>
#define Sca(x) scanf("%d",&x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)
#define Scl2(x,y) scanf("%lld%lld",&x,&y)
#define Scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define Pri(x) printf("%d\n",x)
#define Prl(x) printf("%lld\n",x)
#define For(i,x,y) for(int i=x;i<=y;i++)
#define _For(i,x,y) for(int i=x;i>=y;i--)
#define FAST_IO std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
const double Pi = acos(-1.0);
using namespace std;
template <class T>void tomax(T&a,T b){ a=max(a,b); }  
template <class T>void tomin(T&a,T b){ a=min(a,b); }
const int N=1e5+5;
int T;
int color;
struct Segt{
    #define lc (p<<1)
    #define rc (p<<1|1)
    #define MID (tree[p].l+tree[p].r)>>1
    struct Tree{
        int l,r;
        int have,lz;
        inline void init(int left,int right){ l=left; r=right; have=1; lz=0; }
        inline void updata(int who){ have=who; lz=who; }
        inline void lable(){ color|=have; } 
    }tree[N<<2|1];
    inline void pushdown(int p){ tree[p].have=tree[lc].have|tree[rc].have; }
    inline void pushup(int p){
        tree[lc].updata(tree[p].lz);
        tree[rc].updata(tree[p].lz);
        tree[p].lz=0;
    }
    void build(int l,int r,int p){
        tree[p].init(l,r);
        if(l==r)  return ;
        int mid=MID;
        build(l,mid,lc);
        build(mid+1,r,rc);
    }
    void updata(int l,int r,int p,int who){
        if(tree[p].l>=l&&tree[p].r<=r){
            tree[p].updata(who);
            return ;
        }
        if(tree[p].lz) pushup(p);
        int mid=MID;
        if(l<=mid) updata(l,r,lc,who);
        if(r>mid) updata(l,r,rc,who);
        pushdown(p);
    }
    void getans(int l,int r,int p){
        if(tree[p].l>=l&&tree[p].r<=r){
            tree[p].lable();
            return ;
        }
        if(tree[p].lz) pushup(p);
        int mid=MID;
        if(l<=mid) getans(l,r,lc);
        if(r>mid) getans(l,r,rc);
        return ; 
    }

}t;
int main(){
    int n,m;
    Sca3(n,T,m);
    t.build(1,n,1);
    while(m--){
        char cmd; scanf(" %c",&cmd);
        int A,B; Sca2(A,B);
        if(A>B) swap(A,B); 
        if(cmd=='C'){
            int C; Sca(C); 
            t.updata(A,B,1,1<<(C-1)); 
        }
        else if(cmd=='P'){
            color=0;
            t.getans(A,B,1);
            int sum=0;
            while(color){
                if(color&1) sum++;
                color>>=1;
            }
            Pri(sum);
        }
    }
    return 0;
}