萌新求调线段树

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
//#define LL_inf 1145141919810
#define ull unsigned long long
#define ll long long
using namespace std;
//#define int long long
const int Maxn=1e5+10;
int Ar[Maxn];
int n,m;
//bool debug;
//#define cout if(debug) cout
struct SegmentTree{
	struct Segtree{
		int sum;
		int ans0,ans1;
		int lmax0,rmax0;
		int lmax1,rmax1;
		int len;
		int tag1,tag2;
	}t[Maxn<<2];
	#define ls node<<1
	#define rs node<<1|1
	void pushup(int node)
	{
		t[node].sum=t[ls].sum+t[rs].sum;
		t[node].len=t[ls].len+t[rs].len;
		t[node].ans0=max(max(t[ls].ans0,t[rs].ans0),t[ls].rmax0+t[rs].lmax0);
		t[node].ans1=max(max(t[ls].ans1,t[rs].ans1),t[ls].rmax1+t[rs].lmax1);
		
		t[node].lmax0=t[ls].lmax0;
		if(t[ls].lmax0==t[ls].len)
		{
			t[node].lmax0=t[ls].len+t[rs].lmax0;
		}
		
		t[node].lmax1=t[ls].lmax1;
		if(t[ls].lmax1==t[ls].len)
		{
			t[node].lmax1=t[ls].len+t[rs].lmax1;
		}
		
		t[node].rmax0=t[rs].rmax0;
		if(t[rs].rmax0==t[rs].len)
		{
			t[node].rmax0=t[rs].len+t[ls].rmax0;
		}
		
		t[node].rmax1=t[rs].rmax1;
		if(t[rs].rmax1==t[rs].len)
		{
			t[node].rmax1=t[rs].len+t[ls].rmax1;
		}
	}
	void pushdown(int node)
	{
		if(t[node].tag1!=-1)
		{
			t[ls].tag1=t[rs].tag1=t[node].tag1;
			t[ls].tag2=t[rs].tag2=0;
			if(t[node].tag1==0)
			{
				t[ls].ans0=t[ls].lmax0=t[ls].rmax0=t[ls].len;
				t[rs].ans0=t[rs].lmax0=t[rs].rmax0=t[rs].len;
				t[ls].ans1=t[rs].ans1=0;
				t[ls].lmax1=t[rs].lmax1=t[ls].rmax1=t[rs].rmax1=0;
				t[ls].sum=t[rs].sum=0;
			}else{
				t[ls].sum=t[ls].ans1=t[ls].lmax1=t[ls].rmax1=t[ls].len;
				t[rs].sum=t[rs].ans1=t[rs].lmax1=t[rs].rmax1=t[rs].len;
				t[ls].ans0=t[rs].ans0=0;
				t[ls].lmax0=t[rs].lmax0=t[ls].rmax0=t[rs].rmax0=0;
			}
			
			t[node].tag1=-1;
		}
		
		if(t[node].tag2)
		{
			t[ls].sum=t[ls].len-t[ls].sum;
			t[rs].sum=t[rs].len-t[rs].sum;
			swap(t[ls].ans0,t[ls].ans1);
			swap(t[rs].ans0,t[rs].ans1);
			swap(t[ls].lmax0,t[ls].lmax1);
			swap(t[rs].lmax0,t[rs].lmax1);
			swap(t[ls].rmax0,t[ls].rmax1);
			swap(t[rs].rmax0,t[rs].rmax1);
			
			if(t[ls].tag1==-1)
			{
				t[ls].tag2^=1;
			}else{
				t[ls].tag1^=1;
			}
			
			if(t[rs].tag1==-1)
			{
				t[rs].tag2^=1;
			}else{
				t[rs].tag1^=1;
			}
			
			t[node].tag2=0;
		}
	}
	
	void build(int node,int l,int r)
	{
		t[node].tag1=-1;
		t[node].tag2=0;
		if(l==r)
		{
			t[node].sum=Ar[l];
			if(Ar[l]==0)
			{
				t[node].ans0=t[node].lmax0=t[node].rmax0=1;
				t[node].ans1=t[node].lmax1=t[node].rmax1=0;
			}else{
				t[node].ans0=t[node].lmax0=t[node].rmax0=0;
				t[node].ans1=t[node].lmax1=t[node].rmax1=1;
			}
			t[node].len=1; 
			return ;
		}
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r); 
		pushup(node);
	}
	void assign(int node,int l,int r,int ql,int qr,int val)
	{
		if(ql<=l && r<=qr)
		{
			t[node].tag1=val;
			if(val==0)
			{
				t[node].ans0=t[node].lmax0=t[node].rmax0=t[node].len;
				t[node].ans1=0;
				t[node].sum=0;
				t[node].lmax1=t[node].rmax1=0;
			}else{
				t[node].sum=t[node].ans1=t[node].lmax1=t[node].rmax1=t[node].len;
				t[node].ans0=0;
				t[node].lmax0=t[node].rmax0=0;
			}
			return ;
		}
		pushdown(node);
		int mid=(l+r)>>1;
		if(ql<=mid)
		{
			assign(ls,l,mid,ql,qr,val);
		}
		if(qr>mid)
		{
			assign(rs,mid+1,r,ql,qr,val);
		}
		pushup(node);
	}
	
	void rever(int node,int l,int r,int ql,int qr)
	{
		if(ql<=l && r<=qr)
		{
			t[node].sum=t[node].len-t[node].sum;
			swap(t[node].ans0,t[node].ans1);
			swap(t[node].lmax0,t[node].lmax1);
			swap(t[node].rmax0,t[node].rmax1);
			t[node].tag2^=1;
			return ;
		}
		
		int mid=(l+r)>>1;
		pushdown(node);
		if(ql<=mid)
		{
			rever(ls,l,mid,ql,qr);
		}
		if(qr>mid)
		{
			rever(rs,mid+1,r,ql,qr);
		}
		
		pushup(node);
	}
	
	int querysum(int node,int l,int r,int ql,int qr)
	{
//		if(debug) cout<<node<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl; 
		if(ql<=l && r<=qr)
		{
//			if(debug) cout<<"sum="<<t[node].sum<<endl;
			return t[node].sum;
		}
		int mid=(l+r)>>1;
		pushdown(node);
		int ans=0;
		if(ql<=mid)
		{
			ans+=querysum(ls,l,mid,ql,qr);
		}
		if(qr>mid)
		{
			ans+=querysum(rs,mid+1,r,ql,qr);
		}
		return ans;
	}
	Segtree query(int node,int l,int r,int ql,int qr)
	{
//		cout<<node<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
		if(ql<=l && r<=qr)
		{
			return t[node];
		}
		int mid=(l+r)>>1;
//		cout<<"mid="<<mid<<endl;
		pushdown(node);
		if(qr<=mid)
		{
			return query(ls,l,mid,ql,qr);
		}else if(ql>mid){
			return query(rs,mid+1,r,ql,qr);
		}else{
			Segtree a=query(ls,l,mid,ql,qr);
			Segtree b=query(rs,mid+1,r,ql,qr);
			Segtree c; 
			c.sum=a.sum+b.sum;
			c.len=a.len+b.len;
			c.ans0=max(max(a.ans0,b.ans0),a.rmax0+b.lmax0);
			c.ans1=max(max(a.ans1,b.ans1),a.rmax1+b.lmax1);
			
			c.lmax0=a.lmax0;
			if(a.lmax0==a.len)
			{
				c.lmax0=a.len+b.lmax0;
			}
			
			c.lmax1=a.lmax1;
			if(a.lmax1==a.len)
			{
				c.lmax1=a.len+b.lmax1;
			}
			
			c.rmax0=b.rmax0;
			if(b.rmax0==b.len)
			{
				c.rmax0=b.len+a.rmax0;
			}
			
			c.rmax1=b.rmax1;
			if(b.rmax1==b.len)
			{
				c.rmax1=b.len+a.rmax1;
			}
			
			return c;
		}
	}	
	
	int Query(int l,int r)
	{
		return query(1,1,n,l,r).ans1;
	}
}seg;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&Ar[i]);
	}
	seg.build(1,1,n);
	while(m--)
	{
		int opt,l,r;
		scanf("%d%d%d",&opt,&l,&r);
		l++,r++;
		if(opt==0)
		{
			seg.assign(1,1,n,l,r,0);
		}else if(opt==1){
			seg.assign(1,1,n,l,r,1);
		}else if(opt==2){
			seg.rever(1,1,n,l,r);
		}else if(opt==3){
			printf("%d\n",seg.querysum(1,1,n,l,r));
		}else{
			printf("%d\n",seg.Query(l,r));
		}
//		debug=0;
//		for(int i=1;i<=n;i++)
//		{
//			cout<<seg.querysum(1,1,n,i,i)<<" ";
//		}
//		putchar('\n');
//		debug=1;
	}
	return 0;
}