提交记录:https://www.luogu.com.cn/record/166105173

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+6;
struct Segment_tree {
	int l,r,sum,lmax[2],rmax[2],dat[2],tag[2];//0覆盖,1翻转
} T[maxn<<2];
int n,m;
int c[maxn];
int len(int p) {
	return T[p].r-T[p].l+1;
}
bool check(int p,bool t) {
	return T[p].sum==t*len(p);
}
void pushup(int p) {
	T[p].sum=T[p<<1].sum+T[p<<1|1].sum;
	for(int i=0; i<=1; i++) {
		T[p].lmax[i]=T[p<<1].lmax[i];
		if(check(p<<1,i))
			T[p].lmax[i]=max(T[p].lmax[i],len(p<<1)+T[p<<1|1].lmax[i]);
		T[p].rmax[i]=T[p<<1|1].rmax[i];
		if(check(p<<1|1,i))
			T[p].rmax[i]=max(T[p].rmax[i],len(p<<1|1)+T[p<<1].rmax[i]);
		T[p].dat[i]=max({T[p<<1].dat[i],T[p<<1].rmax[i]+T[p<<1|1].lmax[i],T[p<<1|1].dat[i]});
	}
}
void spread(int p) {
	if(~T[p].tag[0]) {
		int t=T[p].tag[0];
		T[p<<1].sum=len(p<<1),T[p<<1|1].sum=len(p<<1|1);
		T[p<<1].lmax[t]=T[p<<1].rmax[t]=T[p<<1].dat[t]=len(p<<1);
		T[p<<1|1].lmax[t]=T[p<<1|1].rmax[t]=T[p<<1|1].dat[t]=len(p<<1|1);
		T[p<<1].lmax[t^1]=T[p<<1].rmax[t^1]=T[p<<1].dat[t^1]=0;
		T[p<<1|1].lmax[t^1]=T[p<<1|1].rmax[t^1]=T[p<<1|1].dat[t^1]=0;
		T[p<<1].tag[0]=T[p<<1|1].tag[0]=t,T[p<<1].tag[1]=T[p<<1|1].tag[1]=0;
		T[p].tag[0]=-1;
		//puts("f");
	}
	if(T[p].tag[1]) {
		T[p<<1].sum=len(p<<1)-T[p<<1].sum,T[p<<1|1].sum=len(p<<1|1)-T[p<<1|1].sum;
		swap(T[p<<1].lmax[0],T[p<<1].lmax[1]),swap(T[p<<1].rmax[0],T[p<<1].rmax[1]);
		swap(T[p<<1].dat[0],T[p<<1].dat[1]);
		swap(T[p<<1|1].lmax[0],T[p<<1|1].lmax[1]),swap(T[p<<1|1].rmax[0],T[p<<1|1].rmax[1]);
		swap(T[p<<1|1].dat[0],T[p<<1|1].dat[1]);
		//printf("b\n%d %d %d %d %d %d %dj\n",p,T[p].l,T[p].r,T[p<<1].tag[0],T[p<<1].tag[1],T[p<<1|1].tag[0],T[p<<1|1].tag[1]); 
		if(~T[p<<1].tag[0])
			T[p<<1].tag[0]^=1;
		else T[p<<1].tag[1]^=1;
		if(~T[p<<1|1].tag[0])
			T[p<<1|1].tag[0]^=1;
		else T[p<<1|1].tag[1]^=1;
		T[p].tag[1]=0;
		//puts("q");
	}
}
void Build(int p,int l,int r) {
	T[p].l=l,T[p].r=r,T[p].tag[0]=-1,T[p].tag[1]=0;;
	if(l==r) {
		T[p].sum=c[l],T[p].lmax[c[l]]=T[p].rmax[c[l]]=T[p].dat[c[l]]=1;
		return ;
	}
	int mid=l+r>>1;
	Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
	pushup(p);
}
void change(int p,int x,int y,int t) { //0/1:覆盖为0/1,2:翻转
	if(x<=T[p].l&&T[p].r<=y) {
		if(!t) {
			T[p].sum=T[p].lmax[1]=T[p].rmax[1]=T[p].dat[1]=0,T[p].tag[1]=0;
			T[p].lmax[0]=T[p].rmax[0]=T[p].dat[0]=len(p),T[p].tag[0]=0;
		} else if(t==1) {
			T[p].sum=T[p].lmax[1]=T[p].rmax[1]=T[p].dat[1]=len(p),T[p].tag[1]=0;
			T[p].lmax[0]=T[p].rmax[0]=T[p].dat[0]=0,T[p].tag[0]=1;
		} else {
			T[p].sum=len(p)-T[p].sum;
			if(~T[p].tag[0])
				T[p].tag[0]^=1;
			else T[p].tag[1]^=1;
			swap(T[p].lmax[0],T[p].lmax[1]),swap(T[p].rmax[0],T[p].rmax[1]),swap(T[p].dat[0],T[p].dat[1]);
			//printf("%d %d %d %d %d %dp\n",p,T[p].l,T[p].r,t,T[p].dat[0],T[p].dat[1]);
		}
		return ;
	}
	spread(p);
	int mid=T[p].l+T[p].r>>1;
	if(x<=mid)
		change(p<<1,x,y,t);
	if(y>mid)
		change(p<<1|1,x,y,t);
	pushup(p);
}
int ask(int p,int x,int y) {
	if(x<=T[p].l&&T[p].r<=y)
		return T[p].sum;
	spread(p);
	int mid=T[p].l+T[p].r>>1,res=0;
	if(x<=mid)
		res+=ask(p<<1,x,y);
	if(y>mid)
		res+=ask(p<<1|1,x,y);
	return res;
}
Segment_tree query(int p,int x,int y) {
	if(x<=T[p].l&&T[p].r<=y) {
		//printf("%dx %dy %d %d %d %d %dv\n",x,y,p,T[p].l,T[p].r,T[p].dat[0],T[p].dat[1]);
		return T[p];
	}
	spread(p);
	int mid=T[p].l+T[p].r>>1;
	if(x>mid)
		return query(p<<1|1,x,y);
	if(y<=mid)
		return query(p<<1,x,y);
	Segment_tree a,b,res;
	a=query(p<<1,x,y),b=query(p<<1|1,x,y);
	res.sum=a.sum+b.sum;
	res.lmax[1]=a.lmax[1];
	if(a.sum==a.r-a.l+1)
		res.lmax[1]=max(res.lmax[1],len(p<<1)+b.lmax[1]);
	res.rmax[1]=b.rmax[1];
	if(b.sum==b.r-b.l+1)
		res.rmax[1]=max(res.rmax[1],len(p<<1|1)+a.rmax[1]);
	res.dat[1]=max({a.dat[1],a.rmax[1]+b.lmax[1],b.dat[1]});
	//printf("%d %d %dr\n",T[p].l,T[p].r,res.dat[1]);
	return res;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)
		scanf("%d",&c[i]);
	Build(1,1,n);
	int op,l,r;
	while(m--) {
		//for(int i=1; i<=n; i++)
		//	printf("%d ",query(1,i,i).dat[1]);
		//puts("g");
		scanf("%d%d%d",&op,&l,&r),l++,r++;
		if(op<=2)
			change(1,l,r,op);
		else if(op==3)
			printf("%d\n",ask(1,l,r));
		else printf("%d\n",query(1,l,r).dat[1]);
	}
	return 0;
}