Eternality @ 2022-10-26 09:58:01
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,a[N];
struct T
{
int l,r,sum;
int l0,l1,r0,r1;
int g,k1,k0;
int tag1,tag2,tag3;
}t[N<<2];
T update(T &p,T ls,T rs)
{
p.sum=ls.sum+rs.sum;
p.l1=(ls.g==1 ? ls.r-ls.l+1+rs.l1 : ls.l1);
p.l0=(ls.g==2 ? ls.r-ls.l+1+rs.l0 : ls.l0);
p.r1=(rs.g==1 ? rs.r-rs.l+1+ls.r1 : rs.r1);
p.r0=(rs.g==2 ? rs.r-rs.l+1+ls.l0 : rs.r0);
if(p.sum==p.r-p.l+1)p.g=1;
else if(p.sum==0)p.g=2;
else p.g=0;
p.k1=max(max(ls.k1,rs.k1),ls.r1+rs.l1);
p.k0=max(max(ls.k0,rs.k0),ls.r0+rs.l0);
return p;
}
void build(int p,int l,int r)
{
t[p].l=l;
t[p].r=r;
if(l==r)
{
t[p].sum=a[l];
if(a[l]==1)
{
t[p].l1=t[p].r1=1;
t[p].l0=t[p].r0=0;
t[p].g=1;
t[p].k1=1;
t[p].k0=0;
}
else
{
t[p].l0=t[p].r0=1;
t[p].l1=t[p].r1=0;
t[p].g=2;
t[p].k1=0;
t[p].k0=1;
}
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
update(t[p],t[p<<1],t[p<<1|1]);
}
void color(int p,int tag1,int tag2,int tag3)
{
if((tag1&&!tag2&&!tag3)||(!tag1&&tag2&&tag3))
{
t[p].tag1=1;
t[p].tag2=t[p].tag3=0;
t[p].g=2;
t[p].k0=t[p].r-t[p].l+1;
t[p].k1=0;
t[p].l0=t[p].r0=t[p].r-t[p].l+1;
t[p].l1=t[p].r1=0;
t[p].sum=0;
}
if((!tag1&&tag2&&!tag3)||(tag1&&!tag2&&tag3))
{
t[p].tag2=1;
t[p].tag1=t[p].tag3=0;
t[p].g=1;
t[p].k1=t[p].r-t[p].l+1;
t[p].k0=0;
t[p].l1=t[p].r1=t[p].r-t[p].l+1;
t[p].l0=t[p].r0=0;
t[p].sum=t[p].r-t[p].l+1;
}
if(!tag1&&!tag2&&tag3)
{
t[p].tag3=1 xor t[p].tag3;
if(t[p].g==2)t[p].g=1;
if(t[p].g==1)t[p].g=2;
int k0=t[p].k0,k1=t[p].k1;
t[p].k1=k0;
t[p].k0=k1;
int l1=t[p].l1,l0=t[p].l0,r1=t[p].r1,r0=t[p].r0;
t[p].l1=l0;
t[p].l0=l1;
t[p].r0=r1;
t[p].r1=r0;
t[p].sum=t[p].r-t[p].l+1-t[p].sum;
}
}
void pushdown(int p)
{
color(p<<1,t[p].tag1,t[p].tag2,t[p].tag3);
color(p<<1|1,t[p].tag1,t[p].tag2,t[p].tag3);
t[p].tag1=t[p].tag2=t[p].tag3=0;
}
void change(int p,int l,int r,int op)
{
if(l<=t[p].l&&r>=t[p].r)
{
if(op==1)color(p,1,0,0);
if(op==2)color(p,0,1,0);
if(op==3)color(p,0,0,1);
return;
}
pushdown(p);
int mid=t[p].l+t[p].r>>1;
if(l<=mid)change(p<<1,l,r,op);
if(r>mid)change(p<<1|1,l,r,op);
update(t[p],t[p<<1],t[p<<1|1]);
}
T ask(int p,int l,int r)
{
if(l<=t[p].l&&r>=t[p].r)return t[p];
pushdown(p);
T ans;
int mid=t[p].l+t[p].r>>1;
if(l<=mid&&r>mid)return update(ans,ask(p<<1,l,r),ask(p<<1|1,l,r));
if(r<=mid)return ask(p<<1,l,r);
if(l>mid)return ask(p<<1|1,l,r);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,1,n);
while(m--)
{
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
op++,l++,r++;
if(op==1||op==2||op==3)
{
change(1,l,r,op);
}
if(op==4||op==5)
{
if(op==4)cout<<ask(1,l,r).sum<<"\n";
else cout<<ask(1,l,r).k1<<"\n";
}
// cout<<"T: ";
// for(int i=1;i<=n;i++)cout<<a[i]<<" ";
// cout<<endl;
}
return 0;
}