官方题解

题目大意

给定一个长度为 $n$ 的 $01$ 串，有两种查询，第一种查询为反转区间 $[L,R]$ 的 0 和 1 ，第二种查询为判断子串 $[L,R]$ 是否为好字符串，好字符串的定义为字符串中任意连续的 $2$ 个字符都不相同的字符串是好字符串。

解题思路

不妨设长度为 $n-1$ 的序列 $is=(is_1,is_2,...,is_{n-1})$ ，如果 $s_i=s_{i+1}$ ，则让 $is_i=1$ ，否则 $is_i=0$ 。

对于第一种查询 1 L R ，由于区间 $[L,R]$ 内的相邻字符的关系不会发生改变，所以对于整个序列 $is$ ，只有 $L-1$ 和 $R$ 的位置发生改变，即修改 $is_{L-1}$ 为 $1-is_{L-1}$ 以及 $is_{R}$ 为 $1-is_{R}$ 。其中，如果 $L=1$ 或 $R=n$ ，则对应序列位置不发生改变。

对于第二种查询 2 L R ，如果 $is_L = is_{L+1} = \cdots = is_{R-1} = 1$ ，那么答案为 Yes ，否则为 No 。

对于以上操作，可以使用线段树或树状数组进行维护和查询。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18+10;
const ll N = 1000010;

string a;
struct segtree{
    int l,r;
    bool is;
    char cl,cr;
    int lazy;
}tr[N*4];

void pushup(segtree &u,segtree &l,segtree &r){
    u.cl=l.cl;
    u.cr=r.cr;
    if(l.is==false || r.is==false || l.cr==r.cl){
        u.is=false;
    }
    else u.is=true;
}

void pushup(int u){
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}

void pushdown(int u){
    tr[u<<1].lazy^=tr[u].lazy;
    tr[u<<1|1].lazy^=tr[u].lazy;
    if(tr[u].lazy){
        tr[u<<1].cl^=1;
        tr[u<<1].cr^=1;
        tr[u<<1|1].cl^=1;
        tr[u<<1|1].cr^=1;
    }
    tr[u].lazy=0;
}

void build(int u,int l,int r){
    if(l==r){
        tr[u]={l,r,1,a[l],a[l],0};
        return;
    }
    tr[u]={l,r};
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify(int u,int l,int r,int d){
    if(tr[u].l>=l && tr[u].r<=r){
        tr[u].cl^=1;
        tr[u].cr^=1;
        tr[u].lazy^=d;
        return;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) modify(u<<1,l,r,d);
    if(r>mid) modify(u<<1|1,l,r,d);
    pushup(u);
}

segtree query(int u,int l,int r){
    if(tr[u].l>=l && tr[u].r<=r){
        return tr[u];
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(r<=mid) return query(u<<1,l,r);
    else if(l>mid) return query(u<<1|1,l,r);
    else{
        auto left=query(u<<1,l,r);
        auto right=query(u<<1|1,l,r);
        segtree res;
        pushup(res,left,right);
        return res;
    }
}

int main(){
    int n,q;cin>>n>>q;
    cin>>a;a=' '+a;
    build(1,1,n);

    while(q--){
        int op,l,r;cin>>op>>l>>r;
        if(op==1){
            modify(1,l,r,1);
        }
        else{
            if(query(1,l,r).is) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}