RT 过了样例和#11

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=100001;
struct node{
	int l,r,qcnt,hcnt,cnt,qcnt0,hcnt0,cnt0,sum;
	int g,f; 
}tr[N*4];
int a[N];
int n,m;
void pushup(int u)
{
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
	tr[u].cnt=max(max(tr[u<<1].cnt,tr[u<<1|1].cnt),tr[u<<1].hcnt+tr[u<<1|1].qcnt);
	tr[u].cnt0=max(max(tr[u<<1].cnt0,tr[u<<1|1].cnt0),tr[u<<1].hcnt0+tr[u<<1|1].qcnt0);
	tr[u].qcnt=(tr[u<<1].qcnt==(tr[u<<1].r-tr[u<<1].l+1))?tr[u<<1].qcnt+tr[u<<1|1].qcnt:tr[u<<1].qcnt;
	tr[u].hcnt=(tr[u<<1|1].hcnt==(tr[u<<1|1].r-tr[u<<1|1].l+1))?tr[u<<1].hcnt+tr[u<<1|1].hcnt:tr[u<<1|1].hcnt;
	tr[u].qcnt0=(tr[u<<1].qcnt0==(tr[u<<1].r-tr[u<<1].l+1))?tr[u<<1].qcnt0+tr[u<<1|1].qcnt0:tr[u<<1].qcnt0;
	tr[u].hcnt0=(tr[u<<1|1].hcnt0==(tr[u<<1|1].r-tr[u<<1|1].l+1))?tr[u<<1].hcnt0+tr[u<<1|1].hcnt0:tr[u<<1|1].hcnt0;
}
void pushdown_g(int u)
{
	if(tr[u].g!=-1)
	{
	//	cout<<-1;
		int z=u<<1,y=u<<1|1;
		if(tr[u].g==0)
		{
			tr[z].sum=tr[y].sum=0;
			tr[z].cnt=tr[y].cnt=tr[z].qcnt=tr[z].hcnt=tr[y].qcnt=tr[y].hcnt=0;
			tr[z].cnt0=tr[z].qcnt0=tr[z].hcnt0=(tr[z].r-tr[z].l+1);
			tr[y].cnt0=tr[y].qcnt0=tr[y].hcnt0=tr[y].r-tr[y].l+1;
			tr[z].g=tr[y].g=tr[u].g;
		}
		else
		{
			tr[z].sum=(tr[z].r-tr[z].l+1);
			tr[y].sum=(tr[y].r-tr[y].l+1);
			tr[z].cnt0=tr[y].cnt0=tr[z].qcnt0=tr[z].hcnt0=tr[y].qcnt0=tr[y].hcnt0=0;
			tr[z].cnt=tr[z].qcnt=tr[z].hcnt=(tr[z].r-tr[z].l+1);
			tr[y].cnt=tr[y].qcnt=tr[y].hcnt=tr[y].r-tr[y].l+1;
			tr[z].g=tr[y].g=tr[u].g;
		}
		tr[u].g=-1;tr[u].f=0;
	}
}
void pushdown_f(int u)
{
	if(tr[u].f)
	{
	//	cout<<1111111;
		int z=u<<1,y=u<<1|1;
		tr[z].sum=(tr[z].r-tr[z].l+1)-tr[z].sum;
		tr[y].sum=(tr[y].r-tr[y].l+1)-tr[y].sum;
		swap(tr[z].cnt,tr[z].cnt0);
		swap(tr[z].qcnt,tr[z].qcnt0);
		swap(tr[z].hcnt,tr[z].hcnt0);
		swap(tr[y].cnt,tr[y].cnt0);
		swap(tr[y].qcnt,tr[y].qcnt0);
		swap(tr[y].hcnt,tr[y].hcnt0);
		tr[z].f=tr[y].f=1;
		tr[u].f=0;
	}
}
void pushdown(int u)
{	
	pushdown_g(u);
	pushdown_f(u);
}
void build(int u,int l,int r)
{
	if(l==r)
	{
		if(a[l])
			tr[u]={l,r,1,1,1,0,0,0,1,-1,0};
		else 
		 	tr[u]={l,r,0,0,0,1,1,1,0,-1,0};
		return;
	}
	tr[u]={l,r};
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
	//cout<<u<<' '<<tr[u].sum<<endl;
}
void modify_g(int u,int l,int r,int x)
{
	if(l<=tr[u].l&&r>=tr[u].r)
	{
		if(x==0)
		{
			tr[u].sum=0;
			tr[u].cnt=tr[u].qcnt=tr[u].hcnt=0;
			tr[u].cnt0=tr[u].qcnt0=tr[u].hcnt0=(tr[u].r-tr[u].l+1);
		}
		else
		{
			tr[u].sum=(tr[u].r-tr[u].l+1);
			tr[u].cnt0=tr[u].qcnt0=tr[u].hcnt0=0;
			tr[u].cnt=tr[u].qcnt=tr[u].hcnt=(tr[u].r-tr[u].l+1);
		}
		tr[u].g=x;
		//tr[u].f=0;
		return;
	}
	//cout<<tr[u].g<<endl;
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1;
	//cout<<tr[u].g<<' '<<u<<' '<<tr[5].sum<<endl;
	if(l<=mid) modify_g(u<<1,l,r,x);
	if(r>mid) modify_g(u<<1|1,l,r,x);
	pushup(u);
}
void modify_f(int u,int l,int r)
{
	if(l<=tr[u].l&&r>=tr[u].r)
	{
		int z=u;
		tr[z].sum=(tr[z].r-tr[z].l+1)-tr[z].sum;
		swap(tr[z].cnt,tr[z].cnt0);
		swap(tr[z].qcnt,tr[z].qcnt0);
		swap(tr[z].hcnt,tr[z].hcnt0);
		tr[z].f=1;
		return;
	}
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid) modify_f(u<<1,l,r);
	if(r>mid) modify_f(u<<1|1,l,r);
	pushup(u);
}
int query_sum(int u,int l,int r)
{
	if(l<=tr[u].l&&r>=tr[u].r) 
	{
		//cout<<u<<' '<<tr[u].l<<' '<<tr[u].r<<' '<<tr[u].sum<<endl;
		return tr[u].sum;	
	}
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1,sum=0;
	if(l<=mid) sum=query_sum(u<<1,l,r);
	if(r>mid) sum+=query_sum(u<<1|1,l,r);
//	cout<<u<<' '<<sum<<endl;
	return sum;
}
node query(int u,int l,int r)
{
	if(l<=tr[u].l&&r>=tr[u].r) return tr[u];
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1;
	node a={0,0},b={0,0};
	if(l<=mid) a=query(u<<1,l,r);
	if(r>mid) b=query(u<<1|1,l,r);
	if(a.l!=0&&b.l!=0)
	{
		node c={a.l,b.r,(a.qcnt==(a.r-a.l+1)?a.qcnt+b.qcnt:a.qcnt),(b.hcnt==(b.r-b.l+1)?a.hcnt+b.hcnt:b.hcnt),max(max(a.cnt,b.cnt),a.hcnt+b.qcnt),0,0,0,0,0,0};
		return c;
	}
	if(b.l==0) return a;
	return b;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);	
	for(int i=1;i<=N*4;i++) tr[i].g=-1;
	//cout<<tr[5].sum<<endl;
	while(m--)
	{	//cout<<query_sum(1,1,6)<<endl<<endl;
		int opt,l,r;
		cin>>opt>>l>>r;
		//cout<<tr[5].sum<<endl<<endl;
		l++,r++;
		if(opt==0) modify_g(1,l,r,0);
		if(opt==1) modify_g(1,l,r,1);
		if(opt==2) modify_f(1,l,r);
		if(opt==3) cout<<query_sum(1,l,r)<<endl;
		if(opt==4) cout<<query(1,l,r).cnt<<endl;
	}
	return 0;
}