提交信息

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100005],op,l,r,tag[100005<<4],fz[100005<<4];
struct o{
	int s,sum,lsum,rsum;
}tr0[100005<<4],tr1[100005<<4];
void pushup(int c,int l,int r,int mid){
	tr1[c].s=tr1[c<<1].s+tr1[c<<1|1].s;
	tr1[c].sum=max(tr1[c<<1].sum,max(tr1[c<<1|1].sum,tr1[c<<1].rsum+tr1[c<<1|1].lsum));
	if(tr1[c<<1].s==mid-l+1)tr1[c].lsum=tr1[c<<1].s+tr1[c<<1|1].lsum;
	else tr1[c].lsum=tr1[c<<1].lsum;
	if(tr1[c<<1|1].s==r-mid)tr1[c].rsum=tr1[c<<1|1].s+tr1[c<<1].rsum;
	else tr1[c].rsum=tr1[c<<1|1].rsum;
	
	tr0[c].s=tr0[c<<1].s+tr0[c<<1|1].s;
	tr0[c].sum=max(tr0[c<<1].sum,max(tr0[c<<1|1].sum,tr0[c<<1].rsum+tr0[c<<1|1].lsum));
	if(tr0[c<<1].s==mid-l+1)tr0[c].lsum=tr0[c<<1].s+tr0[c<<1|1].lsum;
	else tr0[c].lsum=tr0[c<<1].lsum;
	if(tr0[c<<1|1].s==r-mid)tr0[c].rsum=tr0[c<<1|1].s+tr0[c<<1].rsum;
	else tr0[c].rsum=tr0[c<<1|1].rsum;
}
void build(int l,int r,int c){
	if(l==r){
		tr1[c].s=tr1[c].sum=tr1[c].lsum=tr1[c].rsum=a[l];
		tr0[c].s=tr0[c].sum=tr0[c].lsum=tr0[c].rsum=!a[l];
		tag[c]=-1;
		return;
	}
	int mid=l+r>>1;
	build(l,mid,c<<1),build(mid+1,r,c<<1|1);
	pushup(c,l,r,mid),tag[c]=-1;
}
void pushdown(int c,int l,int r,int mid){
	if(tag[c]!=-1){
		tr1[c<<1].s=tr1[c<<1].sum=tr1[c<<1].lsum=tr1[c<<1].rsum=tag[c]*(mid-l+1);
		tr1[c<<1|1].s=tr1[c<<1|1].sum=tr1[c<<1|1].lsum=tr1[c<<1|1].rsum=tag[c]*(r-mid);
		
		tr0[c<<1].s=tr0[c<<1].sum=tr0[c<<1].lsum=tr0[c<<1].rsum=!tag[c]*(mid-l+1);
		tr0[c<<1|1].s=tr0[c<<1|1].sum=tr0[c<<1|1].lsum=tr0[c<<1|1].rsum=!tag[c]*(r-mid);
		
		tag[c<<1]=tag[c<<1|1]=tag[c];
		tag[c]=-1;
	}
	if(fz[c]){
		swap(tr0[c<<1],tr1[c<<1]);
		swap(tr0[c<<1|1],tr1[c<<1|1]);
		fz[c<<1]=fz[c<<1|1]=fz[c];
		fz[c]=0;
	}
}
void update(int l,int r,int x,int y,int d,int c){
	if(x<=l&&r<=y){
		tag[c]=d;
		fz[c]=0;
		tr1[c].s=tr1[c].sum=tr1[c].lsum=tr1[c].rsum=d*(r-l+1);
		tr0[c].s=tr0[c].sum=tr0[c].lsum=tr0[c].rsum=!d*(r-l+1);
		return;
	}
	int mid=l+r>>1;
	pushdown(c,l,r,mid);
	if(x<=mid)update(l,mid,x,y,d,c<<1);
	if(y>mid)update(mid+1,r,x,y,d,c<<1|1);
	pushup(c,l,r,mid);
}
void updatefz(int l,int r,int x,int y,int c){
	if(x<=l&&r<=y){
		fz[c]^=1;
		swap(tr0[c],tr1[c]);
		return;
	}
	int mid=l+r>>1;
	pushdown(c,l,r,mid);
	if(x<=mid)updatefz(l,mid,x,y,c<<1);
	if(y>mid)updatefz(mid+1,r,x,y,c<<1|1);
	pushup(c,l,r,mid);
}
int querysum(int l,int r,int x,int y,int c){
	if(x<=l&&r<=y)return tr1[c].s;
	int mid=l+r>>1,ans=0;
	pushdown(c,l,r,mid);
	if(x<=mid)ans+=querysum(l,mid,x,y,c<<1);
	if(y>mid)ans+=querysum(mid+1,r,x,y,c<<1|1);
	return ans;
}
o querylx(int l,int r,int x,int y,int c){
	if(x<=l&&r<=y)return tr1[c];
	int mid=l+r>>1;
	pushdown(c,l,r,mid);
	if(y<=mid)return querylx(l,mid,x,y,c<<1);
	if(x>mid)return querylx(mid+1,r,x,y,c<<1|1);
	o t=querylx(l,mid,x,y,c<<1),v=querylx(mid+1,r,x,y,c<<1|1);
	return {t.s+v.s,max(t.sum,max(v.sum,t.rsum+v.lsum)),(t.s==mid-l+1?t.s+v.lsum:t.lsum),(v.s==r-mid?v.s+t.rsum:v.rsum)};
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,n,1);
	while(m--){
		cin>>op>>l>>r,l++,r++;
		if(op-2<0)update(1,n,l,r,op,1);
		if(op==2)updatefz(1,n,l,r,1);
		if(op==3)cout<<querysum(1,n,l,r,1)<<endl;
		if(op==4)cout<<querylx(1,n,l,r,1).sum<<endl;
	}
	return 0;
}