【洛谷P4979】矿洞：坍塌 | Mrsrz's blog

线段树

题目大意：

给定一个序列，每个位置为 A,B,C 中的一种。有两个操作：

1. 区间修改成某种颜色。
2. 给定区间 $l,r$，问区间 $l,r$ 是否满足颜色相同，且 $l-1$ 和 $r+1$ 颜色不同或不存在。

题解：

观察到颜色只有 $3$ 种。那么我们直接状压，每一个二进制位表示一种颜色。

然后用线段树维护区间 or 和，支持区间修改即可。

查询的时候先判区间 or 和是否只有一个二进制位为 1，然后判两边是否相等即可。

时间复杂度 $O(K\log N)$。

Code：

#include<iostream>
using namespace std;
const int N=5e5+8;
int d[N<<2],tag[N<<2],n,m;
char s[N];
void build(int l,int r,int o){
    tag[o]=-1;
    if(l==r)d[o]=1<<s[l]-'A';else{
        const int mid=l+r>>1;
        build(l,mid,o<<1),build(mid+1,r,o<<1|1);
        d[o]=d[o<<1]|d[o<<1|1];
    }
}
inline void pushdown(int o){
    d[o<<1]=d[o<<1|1]=1<<tag[o];
    tag[o<<1]=tag[o<<1|1]=tag[o],tag[o]=-1;
}
void modify(int l,int r,int o,const int&L,const int&R,const int&v){
    if(L<=l&&r<=R)d[o]=1<<v,tag[o]=v;else{
        if(tag[o]!=-1)pushdown(o);
        const int mid=l+r>>1;
        if(L<=mid)modify(l,mid,o<<1,L,R,v);
        if(mid<R)modify(mid+1,r,o<<1|1,L,R,v);
        d[o]=d[o<<1]|d[o<<1|1];
    }
}
int query(int l,int r,int o,const int&L,const int&R){
    if(L<=l&&r<=R)return d[o];
    if(tag[o]!=-1)pushdown(o);
    const int mid=l+r>>1;
    if(L<=mid&&mid<R)return query(l,mid,o<<1,L,R)|query(mid+1,r,o<<1|1,L,R);
    if(L<=mid)return query(l,mid,o<<1,L,R);return query(mid+1,r,o<<1|1,L,R);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>(s+1);
    build(1,n,1);
    cin>>m;
    while(m--){
        int l,r;char op[3];
        cin>>op>>l>>r;
        if(*op=='B'){
            int zt=query(1,n,1,l,r);
            if(__builtin_popcount(zt)>1)
                cout<<"No\n";
            else
                if(l==1||r==n||query(1,n,1,l-1,l-1)!=query(1,n,1,r+1,r+1))
                    cout<<"Yes\n";
                else
                    cout<<"No\n";
        }else{
            cin>>op;
            modify(1,n,1,l,r,*op-'A');
        }
    }
    return 0;
}