线段树题80pts求调 玄关

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+7;
int data[maxn<<2][3];
int lcon[maxn<<2][3];
int rcon[maxn<<2][3];
int mcon[maxn<<2][3];
int tag_cge[maxn<<2];
int tag_swp[maxn<<2];
int n,m,opt,a,b;
int org[maxn];
inline int lson(int x){
	return x<<1;
}
inline int rson(int x){
	return x<<1|1;
}
inline int father(int x){
	return x>>1;
}
inline int length(int l,int r){
	return r-l+1;
}
inline int middle(int l,int r){
	return (l+r)>>1;
}
inline void pushup(int x){
	int ls=lson(x);
	int rs=rson(x);
	for(int kte=0;kte<2;kte++){
		data[x][kte]=data[ls][kte]+data[rs][kte];
		mcon[x][kte]=max(max(mcon[ls][kte],mcon[rs][kte]),lcon[rs][kte]+rcon[ls][kte]);
		if((data[ls][kte]+data[ls][1^kte])==lcon[ls][kte])
			lcon[x][kte]=lcon[ls][kte]+lcon[rs][kte];
		else
			lcon[x][kte]=lcon[ls][kte];
		if((data[rs][kte]+data[rs][1^kte])==rcon[rs][kte])
			rcon[x][kte]=rcon[rs][kte]+rcon[ls][kte];
		else
			rcon[x][kte]=rcon[rs][kte];
	}
}
inline void pushdown(int x,int l,int r){
	int ls=lson(x);
	int rs=rson(x);
	int mid=middle(l,r);
	int lenl=length(l,mid);
	int lenr=length(mid+1,r);
	if(tag_cge[x]){
		int arg=tag_cge[x]-1;
		tag_cge[x]=0;
		tag_cge[ls]=1+arg;
		tag_swp[ls]=0;
		tag_cge[rs]=1+arg;
		tag_swp[rs]=0;
		data[ls][arg]=lenl;
		mcon[ls][arg]=lcon[ls][arg]=rcon[ls][arg]=lenl;
		data[rs][arg]=lenr;
		mcon[rs][arg]=lcon[rs][arg]=rcon[rs][arg]=lenr;
		arg^=1;
		data[ls][arg]=0;
		mcon[ls][arg]=lcon[ls][arg]=rcon[ls][arg]=0;
		data[rs][arg]=0;
		mcon[rs][arg]=lcon[rs][arg]=rcon[rs][arg]=0;
		return;
	}
	if(tag_swp[x]){
		tag_swp[x]=0;
		if(tag_cge[ls])
			tag_cge[ls]=tag_cge[ls]==1?2:1;
		else
			tag_swp[ls]^=1;
		swap(data[ls][1],data[ls][0]);
		swap(lcon[ls][1],lcon[ls][0]);
		swap(mcon[ls][1],mcon[ls][0]);
		swap(rcon[ls][1],rcon[ls][0]);
		if(tag_cge[rs])
			tag_cge[rs]=tag_cge[rs]==1?2:1;
		else
			tag_swp[rs]^=1;
		swap(data[rs][1],data[rs][0]);
		swap(lcon[rs][1],lcon[rs][0]);
		swap(mcon[rs][1],mcon[rs][0]);
		swap(rcon[rs][1],rcon[rs][0]);
		return;
	}
}
void build(int x=1,int l=1,int r=n){
	if(l==r){
		data[x][org[l]]=1;
		mcon[x][org[l]]=lcon[x][org[l]]=rcon[x][org[l]]=1;
		return;
	}
	int mid=middle(l,r);
	build(lson(x),l,mid);
	build(rson(x),mid+1,r);
	pushup(x);
}
void change(int lef,int rig,int arg,int x=1,int l=1,int r=n){
	if(lef<=l&&r<=rig){
		int len=length(l,r);
		tag_cge[x]=1+arg;
		tag_swp[x]=0;
		data[x][arg]=len;
		mcon[x][arg]=lcon[x][arg]=rcon[x][arg]=len;
		arg^=1;
		data[x][arg]=0;
		mcon[x][arg]=lcon[x][arg]=rcon[x][arg]=0;
		return;
	}
	pushdown(x,l,r);
	int mid=middle(l,r);
	if(lef<=mid)
		change(lef,rig,arg,lson(x),l,mid);
	if(mid<rig)
		change(lef,rig,arg,rson(x),mid+1,r);
	pushup(x);
}
void XRswap(int lef,int rig,int x=1,int l=1,int r=n){
	if(lef<=l&&r<=rig){
		int len=length(l,r);
		if(tag_cge[x])
			tag_cge[x]=tag_cge[x]==1?2:1;
		else
			tag_swp[x]^=1;
		swap(data[x][1],data[x][0]);
		swap(lcon[x][1],lcon[x][0]);
		swap(rcon[x][1],rcon[x][0]);
		swap(mcon[x][1],mcon[x][0]);
		return;
	}
	pushdown(x,l,r);
	int mid=middle(l,r);
	if(lef<=mid)
		XRswap(lef,rig,lson(x),l,mid);
	if(mid<rig)
		XRswap(lef,rig,rson(x),mid+1,r);
	pushup(x);
}
int query_data(int lef,int rig,int x=1,int l=1,int r=n){
	if(lef<=l&&r<=rig)
		return data[x][1];
	if(r<lef||rig<l)
		return 0;
	pushdown(x,l,r);
	int res=0;
	int mid=middle(l,r);
	if(lef<=mid)
		res+=query_data(lef,rig,lson(x),l,mid);
	if(mid<rig)
		res+=query_data(lef,rig,rson(x),mid+1,r);
	return res;
}
int query_mcon(int lef,int rig,int x=1,int l=1,int r=n){
	if(lef<=l&&r<=rig)
		return mcon[x][1]; 
	pushdown(x,l,r);
	int res=0;
	int mid=middle(l,r);
	int maxl=0,maxr=0,maxx=0;
	if(lef<=mid-rcon[lson(x)][1])
		maxl=max(maxl,rcon[lson(x)][1]);
	else
		maxl=max(maxl,length(lef,mid));
	if(mid+lcon[rson(x)][1]<rig)
		maxr=max(maxr,lcon[rson(x)][1]);
	else
		maxr=max(maxr,length(mid+1,rig));
	if(lef<=mid)
		maxx=max(maxx,query_mcon(lef,rig,lson(x),l,mid));
	if(mid<rig)
		maxx=max(maxx,query_mcon(lef,rig,rson(x),mid+1,r));
	return max(maxx,maxl+maxr);
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
	#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&org[i]);
	build();
	while(m--){
		scanf("%d%d%d",&opt,&a,&b);
		a++;
		b++;
		if(!opt){
			change(a,b,0);
		}else if(opt==1){
			change(a,b,1);
		}else if(opt==2){
			XRswap(a,b);
		}else if(opt==3){
			printf("%d\n",query_data(a,b));
		}else{
			printf("%d\n",query_mcon(a,b));
		}
	}
	return 0;
}