AC on #1#2#11

#include <bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
	int res = 0,f = 1;
	char ch = getchar();
	while (ch<'0'||ch>'9') f = (ch=='-'?-1:1),ch = getchar();
	while (ch>='0'&&ch<='9') res = (res<<3)+(res<<1)+(ch^48),ch = getchar();
	return res*f;
}
void write(int x)
{
	if (x<0) putchar('-'),x=-x;
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
void writech(int x,char ch){write(x),putchar(ch);}
const int N = 1e5+5;
int n,m;
int a[N];
struct tree
{
	int l,r;
	int sum,lm[2],rm[2],qm[2];
	int rev,cover;
}tr[4*N];
void pushup(int x)
{
	tr[x].sum=tr[2*x].sum+tr[2*x+1].sum;
	tr[x].lm[1]=tr[2*x].lm[1]+(tr[2*x].qm[0]==0)*tr[2*x+1].lm[1];
	tr[x].rm[1]=tr[2*x+1].rm[1]+(tr[2*x+1].qm[0]==0)*tr[2*x].rm[1];
	tr[x].qm[1]=max(max(tr[2*x].qm[1],tr[2*x+1].qm[1]),tr[2*x].rm[1]+tr[2*x+1].lm[1]);
	tr[x].lm[0]=tr[2*x].lm[0]+(tr[2*x].qm[1]==0)*tr[2*x+1].lm[0];
	tr[x].rm[0]=tr[2*x+1].rm[0]+(tr[2*x+1].qm[1]==0)*tr[2*x].rm[0];
	tr[x].qm[0]=max(max(tr[2*x].qm[0],tr[2*x+1].qm[0]),tr[2*x].rm[0]+tr[2*x+1].lm[0]);
}
void bt(int x,int l,int r)
{
	tr[x].l=l,tr[x].r=r;
	tr[x].rev=0;
	tr[x].cover=-1;
	if (l==r)
	{
		tr[x].sum=0;
		tr[x].lm[1]=tr[x].lm[0]=0;
		tr[x].rm[1]=tr[x].rm[0]=0;
		tr[x].qm[1]=tr[x].qm[0]=0;
		if (a[l]==1) tr[x].sum=tr[x].lm[1]=tr[x].rm[1]=tr[x].qm[1]=1;
		else tr[x].lm[0]=tr[x].rm[0]=tr[x].qm[0]=1;
		return ;
	}
	int mid = (l+r)/2;
	bt(2*x,l,mid);
	bt(2*x+1,mid+1,r);
	pushup(x);
}
void pushdown(int x)
{
	if (tr[x].cover!=-1)
	{
		int s = tr[x].cover;
		tr[2*x].sum=(tr[2*x].r-tr[2*x].l+1)*s;
		tr[2*x+1].sum=(tr[2*x+1].r-tr[2*x+1].l+1)*s;
		tr[2*x].cover=tr[2*x+1].cover=s;
		tr[2*x].rev=tr[2*x+1].rev=0;
		tr[2*x].lm[s]=tr[2*x].rm[s]=tr[2*x].qm[s]=tr[2*x].r-tr[2*x].l+1;
		tr[2*x+1].lm[s]=tr[2*x+1].rm[s]=tr[2*x+1].qm[s]=tr[2*x+1].r-tr[2*x+1].l+1;
		s^=1;
		tr[2*x].lm[s]=tr[2*x].rm[s]=tr[2*x].qm[s]=0;
		tr[2*x+1].lm[s]=tr[2*x+1].rm[s]=tr[2*x+1].qm[s]=0;
		tr[x].cover=-1;
		tr[x].rev=0;
	}
	if (tr[x].rev)
	{
		tr[2*x].sum=tr[2*x].r-tr[2*x].l+1-tr[2*x].sum;
		tr[2*x+1].sum=tr[2*x+1].r-tr[2*x+1].l+1-tr[2*x+1].sum;
		if (tr[2*x].cover!=-1) tr[2*x].cover^=1;
		else tr[2*x].rev^=1;
		if (tr[2*x+1].cover!=-1) tr[2*x+1].cover^=1;
		else tr[2*x+1].rev^=1;
		swap(tr[2*x].lm[1],tr[2*x].lm[0]);
		swap(tr[2*x].rm[1],tr[2*x].rm[0]);
		swap(tr[2*x].qm[1],tr[2*x].qm[0]);
		swap(tr[2*x+1].lm[1],tr[2*x+1].lm[0]);
		swap(tr[2*x+1].rm[1],tr[2*x+1].rm[0]);
		swap(tr[2*x+1].qm[1],tr[2*x+1].qm[0]);
		tr[x].rev^=1;
	}
}
void mod(int x,int ql,int qr,int v)
{
	int l = tr[x].l,r = tr[x].r;
	if (ql<=l&&r<=qr)
	{
		tr[x].sum=(r-l+1)*v;
		tr[x].lm[v]=tr[x].rm[v]=tr[x].qm[v]=r-l+1;
		tr[x].lm[v^1]=tr[x].rm[v^1]=tr[x].qm[v^1]=0;
		tr[x].cover=v;
		return ;
	}
	pushdown(x);
	int mid = (l+r)/2;
	if (mid<ql) mod(2*x+1,ql,qr,v);
	else if (qr<=mid) mod(2*x,ql,qr,v);
	else mod(2*x,ql,mid,v),mod(2*x+1,mid+1,qr,v);
	pushup(x);
}
void revers(int x,int ql,int qr)
{
	int l = tr[x].l,r = tr[x].r;
	if (ql<=l&&r<=qr)
	{
		tr[x].sum=r-l+1-tr[x].sum;
		swap(tr[x].lm[1],tr[x].lm[0]);
		swap(tr[x].rm[1],tr[x].rm[0]);
		swap(tr[x].qm[1],tr[x].qm[0]);
		tr[x].rev^=1;
		return ;
	}
	pushdown(x);
	int mid = (l+r)/2;
	if (mid<ql) revers(2*x+1,ql,qr);
	else if (qr<=mid) revers(2*x,ql,qr);
	else revers(2*x,ql,mid),revers(2*x+1,mid+1,qr);
	pushup(x);
}
int query1(int x,int ql,int qr)
{
	int l = tr[x].l,r = tr[x].r;
	if (ql<=l&&r<=qr) return tr[x].sum;
	pushdown(x);
	int mid = (l+r)/2;
	if (mid<ql) return query1(2*x+1,ql,qr);
	else if (qr<=mid) return query1(2*x,ql,qr);
	else return query1(2*x,ql,mid)+query1(2*x+1,mid+1,qr);
}
tree query2(int x,int ql,int qr)
{
	int l = tr[x].l,r = tr[x].r;
	if (ql<=l&&r<=qr) return tr[x];
	pushdown(x);
	int mid = (l+r)/2;
	if (mid<ql) return query2(2*x+1,ql,qr);
	else if (qr<=mid) return query2(2*x,ql,qr);
	else
	{
		tree res;
		tree ll = query2(2*x,ql,mid),rr = query2(2*x+1,mid+1,qr);
		res.l=ll.l,res.r=rr.r;
		res.sum=ll.sum+rr.sum;
		res.lm[1]=ll.lm[1]+(ll.qm[0]==0)*rr.lm[1];
		res.rm[1]=rr.rm[1]+(rr.qm[0]==0)*ll.rm[1];
		res.qm[1]=max(max(ll.qm[1],rr.qm[1]),ll.rm[1]+rr.lm[1]);
		res.lm[0]=ll.lm[0]+(ll.qm[1]==0)*rr.lm[0];
		res.rm[0]=rr.rm[0]+(rr.qm[1]==0)*ll.rm[0];
		res.qm[0]=max(max(ll.qm[0],rr.qm[0]),ll.rm[0]+rr.lm[0]);
		return res;
	}
}
signed main()
{
	n=read(),m=read();
	for (int i = 1; i <= n; i++) a[i]=read();
	bt(1,1,n);
	while (m--)
	{
		int op=read(),l=read()+1,r=read()+1;
		if (op==0) mod(1,l,r,0);
		if (op==1) mod(1,l,r,1);
		if (op==2) revers(1,l,r);
		if (op==3) writech(query1(1,l,r),'\n');
		if (op==4) writech(query2(1,l,r).qm[1],'\n');
	}
	return 0;
}