题解 P1558 【色板游戏】

· · 题解

看大佬们高级的数据结构，似乎对于本蒟蒻来说有些难懂；

我来给初学者们介绍一下STL的bitset。

首先，需要<bitset>头文件。

#include<bitset>
using namespace std;

bitset相当于一个bool数组，但是优点是两个bitset之间可以进行按位运算。

定义方式如下：

bitset<1000>a

初始值是全部设为 0 的。

或者

string s="1010101"
bitset <1000>a1(s);

前面不足位用 0 补足；若字符串长度长于定义长度，只取前面部分。

之后就可以把它当做一个二进制数，进行与、或、非、异或、左右移运算了。

bitset<4> foo (string("1001"));
bitset<4> bar (string("0011"));
foo^=bar; //1010(foo对bar按位异或后赋值给foo)
foo&=bar; //0010(按位与后赋值给foo)
foo|=bar; //0011(按位或后赋值给foo)
foo<<=2;  //1100(左移2位，低位补0，有自身赋值)
foo>>=1;  //0110(右移1位，高位补0，有自身赋值)

另外他还可以实现其他的一些功能。

a.set() //将所有位变成1
a.set(k) //将第k位变成1，超限会报错
a.reset() //清空bitset
a.reset(k) //把第k位变成0
a.flip() //将所有位按位取反
a.flip(k) //将第k位按位取反
a.count() //返回bitset中1的个数
a.all() //若bitset内全是1返回1，否则返回0

比如本题，正好可以利用或的性质：两个数中只要有一个该位上是1，结果的这位上就是1。

详见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<bitset>
using namespace std;
int X,W;char ch;
inline int read()
{
    X=0,W=1;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')W=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){X=(X<<1)+(X<<3)+ch-48;ch=getchar();}
    return X*W;
}
struct tree{
    int l;
    int r;
    int lazy;
    bitset<30>p;
}tr[400001];
bitset<30>ans;
int a[100001];
void pushdown(int k)
{
    if(tr[k].lazy==0)return;
    tr[k<<1].lazy=tr[k].lazy;
    tr[k<<1].p.reset();
    tr[k<<1].p.set(tr[k].lazy,1);
    tr[k<<1|1].lazy=tr[k].lazy;
    tr[k<<1|1].p.reset();
    tr[k<<1|1].p.set(tr[k].lazy,1);
    tr[k].lazy=0;
}
void build(int k)
{
    tr[k].p.set(1,1);
    if(tr[k].l==tr[k].r)return;
    int mid=(tr[k].l+tr[k].r)>>1;
    tr[k<<1].l=tr[k].l;
    tr[k<<1].r=mid;
    tr[k<<1|1].l=mid+1;
    tr[k<<1|1].r=tr[k].r;
    build(k<<1),build(k<<1|1);
}
void change(int k,int l,int r,int c)
{
    if(tr[k].l==l&&tr[k].r==r){
        tr[k].lazy=c;
        tr[k].p.reset();
        tr[k].p.set(c,1);
        return;
    }
    pushdown(k);
    if(l>tr[k<<1].r)change(k<<1|1,l,r,c);
    else if(r<tr[k<<1|1].l)change(k<<1,l,r,c);
    else change(k<<1,l,tr[k<<1].r,c),change(k<<1|1,tr[k<<1|1].l,r,c);
    tr[k].p=(tr[k<<1].p|tr[k<<1|1].p);
}
void ask(int k,int l,int r)
{
    if(tr[k].l==l&&tr[k].r==r){
        ans|=tr[k].p;
        return;
    }
    pushdown(k);
    if(l>tr[k<<1].r)ask(k<<1|1,l,r);
    else if(tr[k<<1|1].l>r)ask(k<<1,l,r);
    else ask(k<<1,l,tr[k<<1].r),ask(k<<1|1,tr[k<<1|1].l,r);
}
int main()
{
    int n=read(),t=read(),m=read();
    tr[1].l=1,tr[1].r=n;
    build(1);
    char op;int u,v,w;
    while(m--){
        scanf(" %c",&op);
        u=read(),v=read();
        if(u>v)swap(u,v);
        switch(op){
            case 'C':{
                w=read();
                change(1,u,v,w);
                break;
            }
            case 'P':{
                ask(1,u,v);
                printf("%d\n",ans.count());
                ans.reset();
                break;
            }
        }
    }
    return 0;
}