题目链接

http://poj.org/problem?id=2777

解题思路

二进制压缩（不知道为啥叫这个名，尽管用到了二进制）
思路不是很好讲，但是你看代码就知道思路了，主要先看树结构体的定义，再看主函数，再看子函数。
理解了本题如何使用的二进制就好理解了。

AC代码

#include<cstdio>
#include<algorithm>

using namespace std;

const int N=1e5+100;

int L,T,O;
struct TREE
{
    int l,r,lazy,num;//lazy=1表示tree.l~tree.r颜色相同，lazy=0表示tree.l~tree.r颜色不同，num，用二进制表示区域内包含的颜色，比如num的二进制为10100，含义为此区域有第2种和第4种颜色。    
}tree[N<<2];
int x,y,col,ans,tmp;
char op;
int lowbit(int i)
{
    return i&(-i);//找最后一个1，会树状数组应该就会这个
}
void Build(int i,int l,int r)
{
    tree[i].l=l;
    tree[i].r=r;
    tree[i].lazy=1;//初始化为区域内颜色相同
    tree[i].num=1<<1;//左移的位数就是第几种颜色
    if(l==r) return ;
    int mid=(l+r)>>1;
    Build(i<<1,l,mid);
    Build(i<<1|1,mid+1,r);
    tree[i].num=tree[i<<1].num|tree[i<<1|1].num;//可有可无，表示大区间颜色的种数是由俩儿子按位或得到的，这也是用二进制的妙处
    return ;
}
void PushDown(int i)
{
    if(tree[i].lazy==0) return ;//相同颜色的区域才会进行psuhdown操作，不同颜色的区域直接return 
    tree[i<<1].lazy=tree[i].lazy;
    tree[i<<1|1].lazy=tree[i].lazy;//传递lazy
    tree[i<<1].num=tree[i].num;//因为区域颜色相同，所以左右儿子的颜色也相同，因此，可以用父亲的num赋值儿子的num//感觉这里理解起来比较难
    tree[i<<1|1].num=tree[i].num;
    tree[i].lazy=0;//归零，表示区域内不再是同一颜色了
    return ;
}
void Update(int i,int l,int r,int c)
{
    if(l<=tree[i].l && tree[i].r<=r)
    {
        tree[i].lazy=1;
        tree[i].num=1<<c;
        return ;
    }
    PushDown(i);//pushdown之后 才能进行染色操作 
    if(tree[i<<1].r>=l) Update(i<<1,l,r,c);
    if(tree[i<<1|1].l<=r) Update(i<<1|1,l,r,c);
    tree[i].num=tree[i<<1].num|tree[i<<1|1].num;
    return ;    
}
int Query(int i,int l,int r)
{

    if(l<=tree[i].l && tree[i].r<=r)
    return tree[i].num;
    if(tree[i].l>r || tree[i].r<l) return 0;
    PushDown(i);
    int ll=0,rr=0;
    if(tree[i<<1].r>=l) ll=Query(i<<1,l,r);//左儿子的颜色数 
    if(tree[i<<1|1].l<=r) rr=Query(i<<1|1,l,r);//右儿子的颜色数
    return ll|rr;//与之前的按位或的意义相同
}
int main()
{
    scanf("%d%d%d",&L,&T,&O);
    Build(1,1,L);
    while(O--)
    {
        getchar();//不能少
        scanf("%c",&op);
        if(op=='C')
        {
            scanf("%d%d%d",&x,&y,&col);
            if(x>y) swap(x,y);//绝对不能少！我服了
            Update(1,x,y,col);
        }
        else if(op=='P')
        {
            scanf("%d%d",&x,&y);
            if(x>y) swap(x,y);//绝对不能少！我服了
            tmp=Query(1,x,y);//得到的是二进制表示的染色结果（这么说其实不严谨，但不知道怎么表达更确切了）
            ans=0;
            while(tmp>0)
            {
                ans++;
                tmp-=lowbit(tmp);//统计有多少个1，即有多少种颜色
            }
            printf("%d\n",ans);
        }
    }
}