POJ 2777/洛谷 P1558 Count Color 题解【线段树】【状态压缩】

点击量：206

    以为是个线段树裸题，结果以为错了……

目录

题目描述

色板长度为L，L是一个正整数，所以我们可以均匀地将它划分成L块1厘米长的小方格。并从左到右标记为1,2,…L。

 

现在色板上只有一个颜色，在色板上只能做两件事：

 

1. “C A B C” 指在A到B号方格中涂上颜色C。
2. “P A B” 指询问：A到B号方格中有几种颜色。

 

学校的颜料盒中一共有T种颜料。为简便起见，我们把他们标记为1,2,…T。开始时色板上原有的颜色就为1号色。

 

输入输出格式

输入格式：

第一行有3个整数L(1<=L<=100000),T(1<=T<=30)和O(1<=O<=100000)。 在这里O表示事件数。
接下来O行, 每行以”C A B C” 或 “P A B” 得形式表示所要做的事情(这里A,B,C为整数,可能会有A>B，这样的话需要你交换A和B)

 

输出格式：

对于老师的提问，做出相应的回答。每行一个整数。

 

输入输出样例

输入样例#1：

2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2

输出样例#1：

2
1

题解：

    以为是一个区间覆盖问题让求有多少段颜色就直接做了，没注意到是“种类”。不过还好$ t\le 30$，可以状压。

    和普通的线段树不同的是，这里的节点维护了一个状态和一个lazy。状态就是这个区间有哪些颜色，用一个int状压。如果有lazy，说明这个区间都要被lazy覆盖，只有这一种颜色，在状态中只有这个颜色代表的位是1。

    需要注意一点，所有节点的初始状压状态都是第0位，代表了第1种颜色。最后查询时要把所有区间或起来，输出popcount()即可。

    popcount代表一个二进制数中1的个数。

Code：

#include<cstdio>
#include<cstring>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
struct node
{
    int l,r,lazy;
    int sta;
    node(int l,int r)
    {
        this->l=l;
        this->r=r;
        sta=1;//初始化
        lazy=0;
    }
    node(){}
}t[400000];
void build(int k,int l,int r)
{
    t[k]=node(l,r);
    if(l==r)
        return;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void pushdown(int k)
{
    if(!t[k].lazy||t[k].l==t[k].r)
        return;
    t[ls].lazy=t[k].lazy;
    t[ls].sta=(1<<t[k].lazy-1);
    t[rs].lazy=t[k].lazy;
    t[rs].sta=(1<<t[k].lazy-1);
    t[k].lazy=0;
}
void change(int k,int l,int r,int x)
{
    if(t[k].l==l&&t[k].r==r)
    {
        t[k].lazy=x;
        t[k].sta=(1<<x-1);
        return;
    }
    pushdown(k);
    if(r<=Mid)
        change(ls,l,r,x);
    else if(l>Mid)
        change(rs,l,r,x);
    else
    {
        change(ls,l,Mid,x);
        change(rs,Mid+1,r,x);
    }
    t[k].sta=t[ls].sta|t[rs].sta;
    return;
}
int ask(int k,int l,int r)
{
    pushdown(k);
    if(l==t[k].l&&r==t[k].r)
        return t[k].sta;
    if(r<=Mid)
        return ask(ls,l,r);
    else if(l>Mid)
        return ask(rs,l,r);
    else
        return ask(ls,l,Mid)|ask(rs,Mid+1,r);
}
int popcount(int x)
{
    int ans=0;
    while(x)
    {
        ans++;
        x-=x&(-x);
    }
    return ans;
}
int main()
{
    int l,t,o,u,v,w;
    char c[20];
    scanf("%d%d%d",&l,&t,&o);
    build(1,1,l);
    for(int i=1;i<=o;i++)
    {
        scanf("%s",c);
        if(c[0]=='C')
        {
            scanf("%d%d%d",&u,&v,&w);
            if(u>v)
            {
                int T=u;
                u=v;
                v=T;
            }
            change(1,u,v,w);
        }
        else
        {
            scanf("%d%d",&u,&v);
            if(u>v)
            {
                int T=u;
                u=v;
                v=T;
            }
            printf("%d\n",popcount(ask(1,u,v)));
        }
    }
    return 0;
}