MnZn20分求调

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,a[N];
struct T{
	int l;
	int r;
	int cnt;
	int cntl;
	int cntm;
	int cntr;
	int cntl_2;
	int cntm_2;
	int cntr_2;
	int lazy; 
	int lazy2;
}t[N*4];
void pushup(int i){
	t[i].cnt=t[i*2].cnt+t[i*2+1].cnt;
	if(t[i*2].cnt==(t[i*2].r-t[i*2].l+1)){
		t[i].cntl=t[i*2].cnt+t[i*2+1].cntl;
	}
	else t[i].cntl=t[i*2].cntl;
	if(t[i*2+1].cnt==(t[i*2+1].r-t[i*2+1].l+1)){
		t[i].cntr=t[i*2+1].cnt+t[i*2].cntr; 
	}
	else t[i].cntr=t[i*2+1].cntr;
	t[i].cntm=max(max(t[i*2].cntm,t[i*2+1].cntm),t[i*2].cntr+t[i*2+1].cntl);
	if(t[i*2].cnt==0){
		t[i].cntl_2=(t[i*2].r-t[i*2].l+1)+t[i*2+1].cntl_2;
	}
	else t[i].cntl_2=t[i*2].cntl_2;
	if(t[i*2+1].cnt==0){
		t[i].cntr_2=(t[i*2+1].r-t[i*2+1].l+1)+t[i*2].cntr_2; 
	}
	else t[i].cntr_2=t[i*2+1].cntr_2;
	t[i].cntm_2=max(max(t[i*2].cntm_2,t[i*2+1].cntm_2),t[i*2].cntr_2+t[i*2+1].cntl_2);
}
void pushdown(int i){
	if(t[i].lazy!=-1){
		t[i].lazy2=0; 
		t[i*2].lazy=t[i].lazy;
		t[i*2+1].lazy=t[i].lazy;
		t[i*2].lazy2=0;
		t[i*2+1].lazy2=0;
		t[i*2].cntl=t[i*2].cntr=t[i*2].cntm=t[i*2].cnt=t[i].lazy*(t[i*2].r-t[i*2].l+1);
		t[i*2].cntl_2=t[i*2].cntm_2=t[i*2].cntr_2=(1-t[i].lazy)*(t[i*2].r-t[i*2].l+1);
		t[i*2+1].cntl=t[i*2+1].cntr=t[i*2+1].cntm=t[i*2+1].cnt=t[i].lazy*(t[i*2+1].r-t[i*2+1].l+1);
		t[i*2+1].cntl_2=t[i*2+1].cntm_2=t[i*2+1].cntr_2=(1-t[i].lazy)*(t[i*2+1].r-t[i*2+1].l+1);
		t[i].lazy=-1;
	}
	if(t[i].lazy2!=0){
	    t[i*2].cnt=(t[i*2].r-t[i*2].l+1)-t[i*2].cnt;
	    t[i*2+1].cnt=(t[i*2+1].r-t[i*2+1].l+1)-t[i*2+1].cnt;
		if(t[i*2].lazy!=-1){
			t[i*2].lazy^=1; 
		}
		else t[i*2].lazy2^=1;
		if(t[i*2+1].lazy!=-1){
			t[i*2+1].lazy^=1;
		}
		else t[i*2+1].lazy2^=1;
		swap(t[i*2].cntl,t[i*2].cntl_2);
		swap(t[i*2].cntm,t[i*2].cntm_2);
		swap(t[i*2].cntr,t[i*2].cntr_2);
		swap(t[i*2+1].cntl,t[i*2+1].cntl_2);
		swap(t[i*2+1].cntm,t[i*2+1].cntm_2);
		swap(t[i*2+1].cntr,t[i*2+1].cntr_2);
		t[i].lazy2=0;
	}
}
void build(int i,int l,int r){
	t[i].l=l;
	t[i].r=r;
	t[i].lazy=-1;
	t[i].lazy2=0;
	if(l==r){
		t[i].cnt=t[i].cntl=t[i].cntm=t[i].cntr=a[l];
		t[i].cntl_2=t[i].cntm_2=t[i].cntr_2=(1-a[l]);
		return;
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	pushup(i);
}
void update(int i,int l,int r,int x){
	if(t[i].l==l&&t[i].r==r){
		if(x==0||x==1){
			t[i].cnt=t[i].cntl=t[i].cntr=t[i].cntm=x*(t[i].r-t[i].l+1);
			t[i].cntl_2=t[i].cntm_2=t[i].cntr_2=(1-x)*(t[i].r-t[i].l+1);
			t[i].lazy=x;
		}
		else{
			t[i].cnt=(t[i].r-t[i].l+1)-t[i].cnt;
			swap(t[i].cntl,t[i].cntl_2);
			swap(t[i].cntm,t[i].cntm_2);
			swap(t[i].cntr,t[i].cntr_2);
			t[i].lazy2^=1;
		}
		return;
	}
	pushdown(i);
	int mid=(t[i].l+t[i].r)/2;
	if(r<=mid){
		update(i*2,l,r,x);
	}
	else if(l>mid){
		update(i*2+1,l,r,x);
	}
	else{
	    update(i*2,l,mid,x);
	    update(i*2+1,mid+1,r,x);
	}
	pushup(i);
}
int query(int i,int l,int r){
	if(t[i].l==l&&t[i].r==r){
		return t[i].cnt;
	}	
	pushdown(i);
	int mid=(t[i].l+t[i].r)/2;
	if(r<=mid){
		return query(i*2,l,r);
	}
	else if(l>mid){
		return query(i*2+1,l,r);
	}
	else{
	    return query(i*2,l,mid)+query(i*2+1,mid+1,r);
	}
}
T query2(int i,int l,int r){
	if(t[i].l==l&&t[i].r==r){
		return t[i];
	}
	pushdown(i);
	T ans;
	int mid=(t[i].l+t[i].r)/2;
	if(r<=mid){
		return query2(i*2,l,r);
	}
	else if(l>mid){
		return query2(i*2+1,l,r);
	}
	else{
		T left=query2(i*2,l,mid);
		T right=query2(i*2+1,mid+1,r);
		ans.cnt=left.cnt+right.cnt;
		if(left.cnt==(left.r-left.l+1)){
			ans.cntl=left.cnt+right.cntl;
		}
		else ans.cntl=left.cntl;
		if(right.cnt==(right.r-right.l+1)){
			ans.cntr=right.cnt+left.cntr; 
		}
		else ans.cntr=right.cntr;
		ans.cntm=max(max(left.cntm,right.cntm),left.cntr+right.cntl);
		if(left.cnt==0){
			ans.cntl_2=(left.r-left.l+1)+right.cntl_2;
		}
		else ans.cntl_2=left.cntl_2;
		if(right.cnt==0){
			ans.cntr_2=(right.r-right.l+1)+left.cntr_2; 
		}
		else ans.cntr_2=right.cntr_2;
		ans.cntm_2=max(max(left.cntm_2,right.cntm_2),left.cntr_2+right.cntl_2);
		return ans;
	}
}
int main(){
	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,x,y;
		cin>>op>>x>>y;
		if(x>y){
		    swap(x,y);
		}
		if(op==0){
			update(1,x+1,y+1,0);
		}
		else if(op==1){
			update(1,x+1,y+1,1);
		}
		else if(op==2){
			update(1,x+1,y+1,2);
		}
		else if(op==3){
			cout<<query(1,x+1,y+1)<<endl;
		}
		else{
			cout<<query2(1,x+1,y+1).cntm<<endl;
		}
	}
	return 0;
}