hack/样例全过

// Problem: P2572 [SCOI2010] 序列操作
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2572
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
//#define int long long
#define ull unsigned long long
#define ll long long
#define MAXN 100019
#define WA cout<<"CCF\n";
#define eps 1e-5
#define ls i*2
#define rs i*2+1
#define none -1145141919
#define pii pair<int,int>
#define Y cout<<"Yes\n"
#define N cout<<"No\n"
#define H cout<<"\n"
struct lxy
{
	int n1,n0;
	int tagr;//reverse
	int tag0,tag1;
	int l,r;
	int lm1,rm1,all1;//all1 for 1
	int lm0,rm0,all0;//all1 for 0
} tree[MAXN*4];
int n,m;
int input[MAXN];
void pr()
{
	cout<<"pr start=\npos_=";
	for(int i=1;i<=25;i++) cout<<setw(2)<<i<<" ";
	cout<<"\nin1_=";
	for(int i=1;i<=25;i++) cout<<setw(2)<<tree[i].n1<<" ";
	cout<<"\ntag1=";
	for(int i=1;i<=25;i++) cout<<setw(2)<<tree[i].tag1<<" ";
	cout<<"\ntagr=";
	for(int i=1;i<=25;i++) cout<<setw(2)<<tree[i].tagr<<" ";
	cout<<"\n------------------\n";
	return ;
}
int dis(int i)
{
	return tree[i].r-tree[i].l+1;
}
void pushup(int i)
{
	tree[i].n1=tree[ls].n1+tree[rs].n1;
	tree[i].n0=tree[ls].n0+tree[rs].n0;
	
	tree[i].lm1=max(tree[ls].lm1,(dis(ls)==tree[ls].n1)*(tree[rs].lm1+tree[ls].n1));
	tree[i].rm1=max(tree[rs].rm1,(dis(rs)==tree[rs].n1)*(tree[ls].rm1+tree[rs].n1));
	tree[i].all1=max({tree[ls].all1,tree[ls].rm1+tree[rs].lm1,tree[rs].all1});
	
	tree[i].lm0=max(tree[ls].lm0,(dis(ls)==tree[ls].n1)*(tree[rs].lm0+tree[ls].n1));
	tree[i].rm0=max(tree[rs].rm0,(dis(rs)==tree[rs].n1)*(tree[ls].rm0+tree[rs].n1));
	tree[i].all0=max({tree[ls].all0,tree[ls].rm0+tree[rs].lm0,tree[rs].all0});
	return ;
}
void build(int i,int l,int r)
{
	tree[i].l=l;
	tree[i].r=r;
	tree[i].tag1=tree[i].tag0=tree[i].tagr=tree[i].lm1=tree[i].rm1=tree[i].all1=0;
	tree[i].lm0=tree[i].rm0=tree[i].all0=0;
	tree[i].n1=tree[i].n0=0;
	if(l==r)
	{
		if(input[l]==1)
		{
			tree[i].n1=1;
			tree[i].n0=0;
			
			tree[i].lm1=tree[i].rm1=tree[i].all1=1;
			tree[i].lm0=tree[i].rm0=tree[i].all0=0;
		}
		else
		{
			tree[i].n0=1;
			tree[i].n1=0;
			
			tree[i].lm1=tree[i].rm1=tree[i].all1=0;
			tree[i].lm0=tree[i].rm0=tree[i].all0=1;
		}
		return ;
	}
	int mid=(l+r)/2;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(i);
	return ;
}
void pushdown(int i)
{
	if(tree[i].tag1)	
	{
		tree[i].tag1=0;
		tree[ls].tag1=tree[rs].tag1=1;
		
		tree[ls].n1=dis(ls);
		tree[ls].n0=0;
		tree[ls].lm1=tree[ls].rm1=tree[ls].all1=dis(ls);
		tree[ls].lm0=tree[ls].rm0=tree[ls].all0=0;
		tree[ls].tag0=0;
		tree[ls].tagr=0;
		
		tree[rs].n1=dis(rs);
		tree[rs].n0=0;
		tree[rs].lm1=tree[rs].rm1=tree[rs].all1=dis(rs);
		tree[rs].lm0=tree[rs].rm0=tree[rs].all0=0;
		tree[rs].tag0=0;
		tree[rs].tagr=0;
	}
	if(tree[i].tag0)
	{
		tree[i].tag0=0;
		tree[ls].tag0=tree[rs].tag0=1;
		
		tree[ls].n0=dis(ls);
		tree[ls].n1=0;
		tree[ls].lm1=tree[ls].rm1=tree[ls].all1=0;
		tree[ls].lm0=tree[ls].rm0=tree[ls].all0=dis(ls);
		tree[ls].tag1=0;
		tree[ls].tagr=0;
		
		tree[rs].n0=dis(rs);
		tree[rs].n1=0;
		tree[rs].lm1=tree[rs].rm1=tree[rs].all1=0;
		tree[rs].lm0=tree[rs].rm0=tree[rs].all0=dis(rs);
		tree[rs].tag1=0;
		tree[rs].tagr=0;
	}
	tree[i].tagr%=2;
	if(tree[i].tagr)
	{
		tree[i].tagr=0;
		tree[ls].tagr++;
		tree[rs].tagr++;
		tree[ls].tagr%=2;
		tree[rs].tagr%=2;
		if(tree[ls].tagr)
		{
			swap(tree[ls].n1,tree[ls].n0);
			swap(tree[ls].lm1,tree[ls].lm0);
			swap(tree[ls].rm1,tree[ls].rm0);
			swap(tree[ls].all1,tree[ls].all0);
			tree[ls].tag1=0;
			tree[ls].tag0=0;
		}
		
		if(tree[rs].tagr)
		{
			swap(tree[rs].n1,tree[rs].n0);
			swap(tree[rs].lm1,tree[rs].lm0);
			swap(tree[rs].rm1,tree[rs].rm0);
			swap(tree[rs].all1,tree[rs].all0);
			tree[rs].tag1=0;
			tree[rs].tag0=0;
		}
	}
	return ;
}
int query_1num(int l,int r,int i)
{
	pushdown(i);
	if(tree[i].l>=l&&tree[i].r<=r) return tree[i].n1;
	if(tree[i].r<l||tree[i].l>r) return 0;
	int ans=0;
	if(tree[ls].r>=l) ans+=query_1num(l,r,ls); 
	if(tree[rs].l<=r) ans+=query_1num(l,r,rs);
	pushup(i);
	return ans; 
}
void get0(int l,int r,int i)
{
	pushdown(i);
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		tree[i].n1=0;
		tree[i].n0=dis(i);
		tree[i].lm1=tree[i].rm1=tree[i].all1=0;
		tree[i].lm0=tree[i].rm0=tree[i].all0=dis(i);
		tree[i].tag1=0;
		tree[i].tag0=1;
		tree[i].tagr=0;
		return ;
	}
	//pushdown(i);
	if(tree[i].r<l||tree[i].l>r) return ;
	if(tree[ls].r>=l) get0(l,r,ls); 
	if(tree[rs].l<=r) get0(l,r,rs);
	pushup(i);
	return ;
}
void get1(int l,int r,int i)
{
	pushdown(i);
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		tree[i].n1=dis(i);
		tree[i].n0=0;
		tree[i].lm1=tree[i].rm1=tree[i].all1=dis(i);
		tree[i].lm0=tree[i].rm0=tree[i].all0=0;
		tree[i].tag1=1;
		tree[i].tag0=0;
		tree[i].tagr=0;
		return ;
	}
	//pushdown(i);
	if(tree[i].r<l||tree[i].l>r) return ;
	if(tree[ls].r>=l) get1(l,r,ls); 
	if(tree[rs].l<=r) get1(l,r,rs);
	pushup(i);
	return ;
}
void rever(int l,int r,int i)
{
	pushdown(i);
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		tree[i].tagr++;
		tree[i].tagr%=2;
		if(tree[i].tagr==0) return ;
		swap(tree[i].n1,tree[i].n0);
		swap(tree[i].lm1,tree[i].lm0);
		swap(tree[i].rm1,tree[i].rm0);
		swap(tree[i].all1,tree[i].all0);
		tree[i].tag1=0;
		tree[i].tag0=0;
		return ;
	}
	//pushdown(i);
	if(tree[i].r<l||tree[i].l>r) return ;
	if(tree[ls].r>=l) rever(l,r,ls); 
	if(tree[rs].l<=r) rever(l,r,rs);
	pushup(i);
	return ;
}
lxy getmax(int l,int r,int i)
{
	pushdown(i);
	if(tree[i].l>=l&&tree[i].r<=r) return tree[i];
	if(tree[ls].r>=r) return getmax(l,r,ls);
	if(tree[rs].l<=l) return getmax(l,r,rs);
	else
	{
		lxy xx1=getmax(l,r,ls);
		lxy yy1=getmax(l,r,rs);
		lxy ne;
		ne.lm1=max(xx1.lm1,(dis(ls)==xx1.n1)*(yy1.lm1+xx1.n1));
		ne.rm1=max(yy1.rm1,(dis(rs)==yy1.n1)*(xx1.rm1+yy1.n1));
		ne.all1=max({xx1.all1,xx1.rm1+yy1.lm1,yy1.all1});
		return ne;
	}
	pushup(i);
} 
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>input[i];
    build(1,1,n);
    //cout<<tree[1].all1<<"\n";
    while(m--)
    {
    	int op,l,r;
    	cin>>op>>l>>r;
    	l++;
    	r++;
    	//pr();
    	switch(op) 
    	{
    		case 0:
    		{
    			get0(l,r,1);
    			break;
    		}
    		case 1:
    		{
    			get1(l,r,1);
    			break;
    		}
    		case 2:
    		{
    			rever(l,r,1);
    			break;
    		}
    		case 3:
    		{
    			cout<<query_1num(l,r,1)<<"\n";
    			break;
    		}
    		case 4:
    		{
    			//WA;
    			cout<<getmax(l,r,1).all1<<"\n";
    			break;
    		}
    	}
    	//pr();
    }
    return 0;
}