ABC341E 题解

· · 题解

题意

给出一个只包含 0 和 1 的字符串，要实现区间取反和检查区间内是否有相邻的相同字符两个操作。

思路

若暴力修改、暴力判断，时间复杂度太大，无法通过本题。

考虑优化，发现题目为区间修改和区间查询，自然想到用线段树来做。

首先考虑区间合并，发现当且仅当左右两区间本身合法，且两区间相邻处不同时，合并后的区间合法。因此线段树要维护区间是否合法和区间左右两端的值。

接着是区间取反，与线段树模板区别不大，只是修改时只需把区间左右两端的值取反，区间的合法性并不改变，最后打上标记即可。

然后是标记的维护与下放。标记也用取反来维护，因为取反偶数次相当于没操作。下放标记时也像修改一样，把两个儿子的左右两端都取反即可。

最后是区间查询，这里需要把左右两部分区间都查询出来再合并，才能得到最终结果。

具体请看代码实现。

代码

其实是比较裸的线段树题，这里用了异或 1 来取反。

#include<iostream>
using namespace std;
const int N=5e5+10;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
int n,Q,t=1,aa[N]; 
char c[N];
struct nod
{
    int l,r;//左儿子编号，右儿子编号 
    bool lf,rf,f,tag;//左右端点的值，区间是否合法，懒惰标记 
}a[N*2];//线段树记得开两倍空间
void pushup(nod &u,nod lc,nod rc)
{
    if(lc.rf!=rc.lf&&lc.f&&rc.f)
        u.f=true;
    else
        u.f=false; 
    u.lf=lc.lf,u.rf=rc.rf;
} //合并操作 
void pushdown(int u)
{
    if(a[u].tag==0)
        return;
    int lc=a[u].l,rc=a[u].r;
    a[lc].lf^=1,a[rc].lf^=1,a[lc].rf^=1,a[rc].rf^=1;
    a[lc].tag^=1,a[rc].tag^=1,a[u].tag=0;
} //标记下放 
void build(int u,int l,int r)
{
    if(l==r)
    {
        a[u].lf=a[u].rf=aa[l],a[u].f=true;
        return;
    }
    int mid=(l+r)/2;
    a[u].l=++t;
    build(t,l,mid);
    a[u].r=++t;
    build(t,mid+1,r);
    pushup(a[u],a[a[u].l],a[a[u].r]);
} //建树 
void change(int u,int l,int r,int ll,int rr)
{
    if(l>=ll&&r<=rr)
    {
        a[u].lf^=1,a[u].rf^=1,a[u].tag^=1;
        return;
    }
    int mid=(l+r)/2;
    pushdown(u);
    if(ll<=mid)
        change(a[u].l,l,mid,ll,rr);
    if(rr>mid)
        change(a[u].r,mid+1,r,ll,rr);
    pushup(a[u],a[a[u].l],a[a[u].r]);
} //区间取反 
nod check(int u,int l,int r,int ll,int rr)
{
    if(l>=ll&&r<=rr)
        return a[u];
    int mid=(l+r)/2;
    pushdown(u);
    if(rr<=mid)
        return check(a[u].l,l,mid,ll,rr);
    if(ll>mid)
        return check(a[u].r,mid+1,r,ll,rr);
    nod ta=check(a[u].l,l,mid,ll,rr),tb=check(a[u].r,mid+1,r,ll,rr),res;
    pushup(res,ta,tb);
    return res;
} //区间判断 
signed main()
{
    n=read(),Q=read();
    cin>>c;
    for(int i=1;i<=n;i++)
        aa[i]=c[i-1]-'0';
    build(1,1,n);
    while(Q--)
    {
        int opt=read(),l=read(),r=read();
        if(opt==1)
            change(1,1,n,l,r);
        else
        {
            nod ans=check(1,1,n,l,r);
            if(ans.f)
                cout<<"Yes"<<"\n";
            else
                cout<<"No"<<"\n";
        }
    }
    return 0;
}