POJ 2777 Count Color

タイトルリンク:http://poj.org/problem?id=2777
标题:一面の長さlenの壁を与えて、最初の色は1で、2種類の操作を行って、1つは[l,r]を色pに塗って、2つは[l,r]区間に全部で何種類の色があるかを尋ねることです
考え方:区間の修正や問い合わせをすると線分樹を使いやすいのですが、どのくらいの色を保存しているのでしょうか、色が30種類未満なので(私はまた題解を見ました)、ビット演算で状態圧縮ができますが、残りは線分樹の普通の区間の修正と更新です(問題を書くときに花式が間違っていて、夜は興奮しすぎたでしょう......)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100030
using namespace std;

struct Tree
{
    int l,r,date;
}tree[maxn*3];

int lazy[maxn*3];

void build(int root,int l,int r)
{
    tree[root].l=l;
    tree[root].r=r;
    if (l==r)
    {
        tree[root].date=(1<<1);
        return;
    }
    int mid=(l+r)>>1;
    build (root<<1,l,mid);
    build (root<<1|1,mid+1,r);
    tree[root].date=tree[root<<1].date|tree[root<<1|1].date;
}

void update(int root,int l,int r,int val)
{

    if (tree[root].l>=l && tree[root].r<=r)
    {
        tree[root].date=(1<<val);
        lazy[root]=(1<<val);
        return;
    }

    if (lazy[root]!=0)
    {
        tree[root<<1].date=tree[root].date;
        tree[root<<1|1].date=tree[root].date;
        lazy[root<<1]=lazy[root];
        lazy[root<<1|1]=lazy[root];
        lazy[root]=0;
    }
    int mid=(tree[root].l+tree[root].r)>>1;

    if (l<=mid) update(root<<1,l,r,val);
    if (r>mid) update(root<<1|1,l,r,val);
    tree[root].date=tree[root<<1].date|tree[root<<1|1].date;
}

int que(int root,int l,int r)
{

    if (lazy[root]!=0) return lazy[root];

    if (tree[root].l==l && tree[root].r==r)
     return tree[root].date;

    int mid=(tree[root].l+tree[root].r)>>1;
    if (r<=mid) return que(root<<1,l,r);
    else if (l>mid) return que(root<<1|1,l,r);
    else return que(root<<1,l,mid)|que(root<<1|1,mid+1,r);

}

int main()
{
    int len,n,m;
    while (scanf("%d%d%d",&len,&n,&m)!=EOF)
    {
        memset(lazy,0,sizeof(lazy));
        build (1,1,len);
        for (int i=0;i<m;i++)
        {
            char tem;
            cin>>tem;
            if (tem=='C')
            {
                int a,b,p;
                scanf("%d%d%d",&a,&b,&p);
                if (a>b) swap(a,b);
                update(1,a,b,p);
            }
            else
            {
                int a,b,res=0,cl;
                scanf("%d%d",&a,&b);
                if (a>b) swap(a,b);
                cl=que(1,a,b);
              //  cout<<":"<<cl<<endl;
                for (int i=1;i<=n;i++)
                {
                    if ((cl&(1<<i))!=0) res++;
                }
                printf("%d
",res);
            }
        }
    }
}