求调 玄关

#include<iostream>

using namespace std;

#define N 100010

int n,m;
int a[N];

struct node{
	int l,r,m,s;
};

struct Tree{
	int s,t;
	node o,z;
	int la1,la2;
	void init()
	{
		s=0,t=0,o.l=0,o.r=0,o.m=0,o.s=0,z.l=0,z.r=0,z.m=0,z.s=0,la1=-1,la2=0;
	}
}d[N*4];

Tree merge(Tree L,Tree R)
{
	Tree ans;
	ans.init();
	int lenl=L.t-L.s+1,lenr=R.t-R.s+1;
	
	if(L.o.s==lenl) ans.o.l=lenl+R.o.l;
	else ans.o.l=L.o.l;
	if(L.z.s==lenl) ans.z.l=lenl+R.z.l;
	else ans.z.l=L.z.l;
	if(R.o.s==lenr) ans.o.r=lenr+L.o.r;
	else ans.o.r=R.o.r;
	if(R.z.s==lenr) ans.z.r=lenr+L.z.r;
	else ans.z.r=R.z.r;
	
	ans.o.m=max(max(L.o.m,R.o.m),L.o.r+R.o.l);
	ans.z.m=max(max(L.z.m,R.z.m),L.z.r+R.z.l);
	
	ans.o.s=L.o.s+R.o.s;
	ans.z.s=L.z.s+R.z.s;
	
	return ans;
}

void build(int s,int t,int p)
{
	d[p].init();
	if(s==t)
	{
		d[p].s=s,d[p].t=t;
		if(a[s]==1)
		{
			d[p].o.l=d[p].o.r=d[p].o.s=d[p].o.m=1;
		}
		else
		{
			d[p].z.l=d[p].z.r=d[p].z.s=d[p].z.m=1;
		}
		return ;
	}
	int mid=s+((t-s)>>1);
	build(s,mid,p*2);
	build(mid+1,t,p*2+1);
	d[p]=merge(d[p*2],d[p*2+1]);
	d[p].s=s,d[p].t=t;
}

void push_down(int s,int t,int p)
{
	int mid=s+((t-s)>>1);
	int lenl=mid-s+1,lenr=t-mid;
	if(d[p].la1!=-1)
	{
		if(d[p].la1==0)
		{
			d[p*2].la1=0,d[p*2].la2=0;
			d[p*2].z.l=d[p*2].z.r=d[p*2].z.m=d[p*2].z.s=lenl;
			d[p*2].o.l=d[p*2].o.r=d[p*2].o.m=d[p*2].o.s=0;
			d[p*2+1].la1=0,d[p*2+1].la2=0;
			d[p*2+1].z.l=d[p*2+1].z.r=d[p*2+1].z.m=d[p*2+1].z.s=lenr;
			d[p*2+1].o.l=d[p*2+1].o.r=d[p*2+1].o.m=d[p*2+1].o.s=0;
		}
		else if(d[p].la1==1)
		{
			d[p*2].la1=1,d[p*2].la2=0;
			d[p*2].z.l=d[p*2].z.r=d[p*2].z.m=d[p*2].z.s=0;
			d[p*2].o.l=d[p*2].o.r=d[p*2].o.m=d[p*2].o.s=lenl;
			d[p*2+1].la1=1,d[p*2+1].la2=0;
			d[p*2+1].z.l=d[p*2+1].z.r=d[p*2+1].z.m=d[p*2+1].z.s=0;
			d[p*2+1].o.l=d[p*2+1].o.r=d[p*2+1].o.m=d[p*2+1].o.s=lenr;
		}
		d[p*2].la1=d[p*2+1].la1=d[p].la1;
		d[p*2].la2=d[p*2+1].la2=0;
		
		d[p].la1=-1;
	}
	if(d[p].la2!=0){
		d[p*2].la2^=1,d[p*2+1].la2^=1;
		if(d[p*2].la1!=-1) d[p*2].la1^=1;
		if(d[p*2+1].la1!=-1) d[p*2+1].la1^=1;
		swap(d[p*2].o,d[p*2].z);
		swap(d[p*2+1].o,d[p*2+1].z);
		d[p].la2=0;
	}
}

void update(int l,int r,int s,int t,int p,int op)
{
	if(l<=s&&t<=r)
	{
		int len=t-s+1;
		if(op==0)
		{
			d[p].la1=0,d[p].la2=0;
			d[p].z.l=d[p].z.r=d[p].z.m=d[p].z.s=len;
			d[p].o.l=d[p].o.r=d[p].o.m=d[p].o.s=0;
		}
		else if(op==1)
		{
			d[p].la1=1,d[p].la2=0;
			d[p].z.l=d[p].z.r=d[p].z.m=d[p].z.s=0;
			d[p].o.l=d[p].o.r=d[p].o.m=d[p].o.s=len;
		}
		else
		{
			if(d[p].la1!=-1) d[p].la1^=1;
			d[p].la2^=1;
			swap(d[p].o,d[p].z);
		}
		return ;
	}
	
	int mid=s+((t-s)>>1);
	
	push_down(s,t,p);
	
	if(mid>=l) update(l,r,s,mid,p*2,op);
	if(mid<r) update(l,r,mid+1,t,p*2+1,op);
	
	d[p]=merge(d[p*2],d[p*2+1]);
	d[p].s=s,d[p].t=t;
}

int get_sum(int l,int r,int s,int t,int p,int op)
{
	if(l<=s&&t<=r)
	{
		if(op==3) return d[p].o.s;
		if(op==4) return max(max(d[p].o.l,d[p].o.r),d[p].o.m);
	}
	
	int mid=s+((t-s)>>1);
	
	push_down(s,t,p);
	
	int sum=0;
	if(mid>=l) sum+=get_sum(l,r,s,mid,p*2,op);
	if(mid<r) sum+=get_sum(l,r,mid+1,t,p*2+1,op);
	
	return sum;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,n,1);
	
	while(m--)
	{
		int op,l,r;
		scanf("%d%d%d",&op,&l,&r);
		l++,r++;
		if(op<3)
		{
			update(l,r,1,n,1,op);
		}
		else
		{
			printf("%d\n",get_sum(l,r,1,n,1,op));
		}
	}
	
	return 0;
}

不能及时回复望谅解