本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-17 22:41:06

题意

给出一个只包含 $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;
}