求调

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int a[N];
struct{
	int l0,l1,r0,r1,m0,m1;
	int sum0,sum1;
	int l,r;
}tree[N<<2];
int tag[N<<2];
int tag1[N<<2];
int ls(int p){
	return p<<1;
}
int rs(int p){
	return p<<1|1;
}
void addtag0(int p,int pl,int pr){
	tree[p].sum0=(tree[p].r-tree[p].l+1);
	tree[p].sum1=0;
	tree[p].l0=tree[p].r-tree[p].l+1;
	tree[p].l1=0;
	tree[p].r0=tree[p].r-tree[p].l+1;
	tree[p].r1=0;
	tree[p].m0=tree[p].r-tree[p].l+1;
	tree[p].m1=0;
	tag[p]=-1;
	return;
}
void addtag1(int p,int pl,int pr){
	tree[p].sum1=(tree[p].r-tree[p].l+1);
	tree[p].sum0=0;
	tree[p].l1=tree[p].r-tree[p].l+1;
	tree[p].l0=0;
	tree[p].r1=tree[p].r-tree[p].l+1;
	tree[p].r0=0;
	tree[p].m1=tree[p].r-tree[p].l+1;
	tree[p].m0=0;
	tag[p]=1;
	return;
}
void addtagc(int p,int pl,int pr){
	swap(tree[p].sum0,tree[p].sum1);
	swap(tree[p].l0,tree[p].l1);
	swap(tree[p].r0,tree[p].r1);
	swap(tree[p].m0,tree[p].m1);
	tag1[p]++;
	return;
}
void push_down0(int p,int pl,int pr){
	if(tag[p]==-1){
		int mid=(pl+pr)>>1;
		addtag0(ls(p),pl,mid);
		addtag0(rs(p),mid+1,pr);
		tag[p]=0;
	}
	return;
}
void push_down1(int p,int pl,int pr){
	if(tag[p]==1){
		int mid=(pl+pr)>>1;
		addtag1(ls(p),pl,mid);
		addtag1(rs(p),mid+1,pr);
		tag[p]=0;
	}
	return;
}
void push_downc(int p,int pl,int pr){
	tag1[p]%=2;
	if(tag1[p]){
		int mid=(pl+pr)>>1;
		addtagc(ls(p),pl,mid);
		addtagc(rs(p),mid+1,pr);
		tag1[p]=0;
	}
	return;
}
void push_up(int p){
	tree[p].sum0=tree[ls(p)].sum0+tree[rs(p)].sum0;
	tree[p].sum1=tree[ls(p)].sum1+tree[rs(p)].sum1;
	if(tree[ls(p)].l0==tree[ls(p)].r-tree[ls(p)].l+1){
		tree[p].l0=tree[ls(p)].l0+tree[rs(p)].l0;
	}else{
		tree[p].l0=tree[ls(p)].l0;
	}
	if(tree[ls(p)].l1==tree[ls(p)].r-tree[ls(p)].l+1){
		tree[p].l1=tree[ls(p)].l1+tree[rs(p)].l1;
	}else{
		tree[p].l1=tree[ls(p)].l1;
	}
	if(tree[rs(p)].r0==tree[rs(p)].r-tree[rs(p)].l+1){
		tree[p].r0=tree[rs(p)].r0+tree[ls(p)].r0;
	}else{
		tree[p].r0=tree[rs(p)].r0;
	}
	if(tree[rs(p)].r1==tree[rs(p)].r-tree[rs(p)].l+1){
		tree[p].r1=tree[rs(p)].r1+tree[ls(p)].r1;
	}else{
		tree[p].r1=tree[rs(p)].r1;
	}
	tree[p].m0=max(tree[ls(p)].m0,tree[rs(p)].m0);
	tree[p].m1=max(tree[ls(p)].m1,tree[rs(p)].m1);
	tree[p].m0=max(tree[p].m0,tree[ls(p)].r0+tree[rs(p)].l0);
	tree[p].m1=max(tree[p].m1,tree[ls(p)].r1+tree[rs(p)].l1);
	return;
}
void update0(int p,int L,int R,int pl,int pr){
	if(L<=pl&&pr<=R){
		addtag0(p,pl,pr);
		return;
	}
	int mid=(pl+pr)>>1;
	push_down0(p,pl,pr);
	push_down1(p,pl,pr);
	push_downc(p,pl,pr);
	if(L<=mid){
		update0(ls(p),L,R,pl,mid);
	}
	if(R>mid){
		update0(rs(p),L,R,mid+1,pr);
	}
	push_up(p);
}
void update1(int p,int L,int R,int pl,int pr){
	if(L<=pl&&pr<=R){
		addtag1(p,pl,pr);
		return;
	}
	int mid=(pl+pr)>>1;
	push_down0(p,pl,pr);
	push_down1(p,pl,pr);
	push_downc(p,pl,pr);
	if(L<=mid){
		update1(ls(p),L,R,pl,mid);
	}
	if(R>mid){
		update1(rs(p),L,R,mid+1,pr);
	}
	push_up(p);
}
void updatec(int p,int L,int R,int pl,int pr){
	if(L<=pl&&pr<=R){
		addtagc(p,pl,pr);
		return;
	}
	int mid=(pl+pr)>>1;
	push_down0(p,pl,pr);
	push_down1(p,pl,pr);
	push_downc(p,pl,pr);
	if(L<=mid){
		updatec(ls(p),L,R,pl,mid);
	}
	if(R>mid){
		updatec(rs(p),L,R,mid+1,pr);
	}
	push_up(p);
}
int query1(int p,int L,int R,int pl,int pr){
	if(L<=pl&&pr<=R){
		return tree[p].sum1;
	}
	int mid=(pl+pr)>>1,res=0;
	push_down0(p,pl,pr);
	push_down1(p,pl,pr);
	push_downc(p,pl,pr);
	if(L<=mid){
		res+=query1(ls(p),L,R,pl,mid);
	}
	if(R>mid){
		res+=query1(rs(p),L,R,mid+1,pr);
	}
	return res;
}
int query2(int p,int L,int R,int pl,int pr){
	if(L<=pl&&pr<=R){
		return tree[p].m1;
	}
	int mid=(pl+pr)>>1,res=0;
	push_down0(p,pl,pr);
	push_down1(p,pl,pr);
	push_downc(p,pl,pr);
	int l=tree[ls(p)].r1,r=tree[rs(p)].l1;
	l=min(l,tree[ls(p)].r-L+1);
	r=min(r,R-tree[rs(p)].l+1);
	res=max(res,l+r);
	if(L<=mid){
		res=max(res,query2(ls(p),L,R,pl,mid));
	} 
	if(R>mid){
		res=max(res,query2(rs(p),L,R,mid+1,pr));
	}
	return res;
}
void build(int p,int pl,int pr){
	tree[p].l=pl;
	tree[p].r=pr;
	if(pl==pr){
		if(a[pl]==0){
			tree[p].l0=1;
			tree[p].r0=1;
			tree[p].m0=1;
			tree[p].sum0=1;
		}else{
			tree[p].l1=1;
			tree[p].r1=1;
			tree[p].m1=1;
			tree[p].sum1=1;
		}
		return;
	}
	int mid=(pl+pr)>>1;
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
	push_up(p);
}
int main(){
//	freopen("A.in","r",stdin);
//	freopen("A.out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op,l,r;
		cin>>op>>l>>r;
		l++,r++;
		if(op==0){
			update0(1,l,r,1,n);
		}else if(op==1){
			update1(1,l,r,1,n);
		}else if(op==2){
			updatec(1,l,r,1,n);
		}else if(op==3){
			cout<<query1(1,l,r,1,n)<<endl;
		}else if(op==4){
			cout<<query2(1,l,r,1,n)<<endl;
		}
	}
	return 0;
}
/*
9 1
0 0 0 1 1 0 1 1 1
4 1 5
*/