_XiAo__ @ 2024-05-10 19:43:34
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
int l,r,v,tag,rev,l0,l1,r0,r1,m0,m1,ifemp,f;
};
int n,m,a,b,c,d,var[500005],N=1;
node t[1600000],mid,emp;
int ls(int idx)
{
return idx*2;
}
int rs(int idx)
{
return idx*2+1;
}
int fa(int idx)
{
return idx>>1;
}
int len(int idx)
{
return t[idx].r-t[idx].l+1;
}
int other(int idx)
{
if(idx&1)return idx-1;
return idx+1;
}
int rev_tag(int k)
{
if(!k)return 0;
if(k==1)return 2;
if(k==2)return 1;
}
void addtag(int idx,int k)
{
if(k==1)t[idx]={t[idx].l,t[idx].r,0,1,0,len(idx),0,len(idx),0,len(idx),0,1,idx};
if(k==2)t[idx]={t[idx].l,t[idx].r,len(idx),2,0,0,len(idx),0,len(idx),0,len(idx),1,idx};
if(k==3)t[idx]={t[idx].l,t[idx].r,len(idx)-t[idx].v,t[idx].tag,!t[idx].rev,t[idx].l1,t[idx].l0,t[idx].r1,t[idx].r0,t[idx].m1,t[idx].m0,1,idx};
return;
}
void merge(int idx)
{
t[idx].v=t[ls(idx)].v+t[rs(idx)].v;
t[idx].l0=t[ls(idx)].l0;
if(t[ls(idx)].l0==len(ls(idx)))t[idx].l0+=t[rs(idx)].l0;
t[idx].l1=t[ls(idx)].l1;
if(t[ls(idx)].l1==len(ls(idx)))t[idx].l1+=t[rs(idx)].l1;
t[idx].r0=t[rs(idx)].r0;
if(t[rs(idx)].r0==len(rs(idx)))t[idx].r0+=t[ls(idx)].r0;
t[idx].r1=t[rs(idx)].r1;
if(t[rs(idx)].r1==len(rs(idx)))t[idx].r1+=t[ls(idx)].r1;
t[idx].m0=max(t[ls(idx)].r0+t[rs(idx)].l0,max(t[ls(idx)].m0,t[rs(idx)].m0));
t[idx].m1=max(t[ls(idx)].r1+t[rs(idx)].l1,max(t[ls(idx)].m1,t[rs(idx)].m1));
return;
}
node node_merge(node a,node b)
{
if(!a.ifemp)return b;
if(!b.ifemp)return a;
if(!a.ifemp and !b.ifemp)return emp;
mid.l0=a.l0;
if(a.l0==len(a.f))mid.l0+=b.l0;
mid.l1=a.l1;
if(a.l1==len(a.f))mid.l1+=b.l1;
mid.r0=b.r0;
if(b.r0==len(b.f))mid.r0+=a.r0;
mid.r1=b.r1;
if(b.r1==len(b.f))mid.r1+=a.r1;
mid.m0=max(a.r0+b.l0,max(a.m0,b.m0));
mid.m1=max(a.r1+b.l1,max(a.m1,b.m1));
return mid;
}
void push_down(int idx)
{
if(t[idx].tag==0 and t[idx].rev==0)return;
addtag(ls(idx),t[idx].tag);
addtag(rs(idx),t[idx].tag);
t[idx].tag=0;
if(!t[idx].rev)return;
addtag(ls(idx),3);
addtag(rs(idx),3);
t[idx].rev=0;
return;
}
bool all_in(int l1,int r1,int l2,int r2)
{
if(l1>=l2 and r1<=r2)return true;
return false;
}
bool all_out(int l1,int r1,int l2,int r2)
{
if(l1>r2 or r1<l2)return true;
return false;
}
int query(int L,int R,int idx)
{
if(all_in(t[idx].l,t[idx].r,L,R))return t[idx].v;
if(all_out(t[idx].l,t[idx].r,L,R))return 0;
push_down(idx);
return query(L,R,ls(idx))+query(L,R,rs(idx));
}
node query2(int L,int R,int idx)
{
if(all_in(t[idx].l,t[idx].r,L,R))return t[idx];
if(all_out(t[idx].l,t[idx].r,L,R))return emp;
push_down(idx);
return node_merge(query2(L,R,ls(idx)),query2(L,R,rs(idx)));
}
void update(int L,int R,int k,int idx)
{
if(all_in(t[idx].l,t[idx].r,L,R))
{
addtag(idx,k);
return;
}
if(all_out(t[idx].l,t[idx].r,L,R))return;
push_down(idx);
update(L,R,k,ls(idx));
update(L,R,k,rs(idx));
merge(idx);
return;
}
void start()
{
cin>>n>>m;
while(n>N)N*=2;
for(int i=1;i<=n;i++)cin>>var[i];
t[1].l=1;
t[1].r=N;
for(int i=1;i<N;i++)
{
t[ls(i)].l=t[i].l;
t[ls(i)].r=t[i].l+(len(i)>>1)-1;
t[rs(i)].l=t[ls(i)].r+1;
t[rs(i)].r=t[i].r;
}
for(int i=1;i<=N+n-1;i++)t[i].ifemp=1;
for(int i=1;i<=N+n-1;i++)t[i].f=i;
for(int i=N;i<=N+n-1;i++)t[i].v=var[i-N+1];
for(int i=N;i<=N+n-1;i++)t[i].l0=!t[i].v;
for(int i=N;i<=N+n-1;i++)t[i].r0=!t[i].v;
for(int i=N;i<=N+n-1;i++)t[i].m0=!t[i].v;
for(int i=N;i<=N+n-1;i++)t[i].l1=t[i].v;
for(int i=N;i<=N+n-1;i++)t[i].r1=t[i].v;
for(int i=N;i<=N+n-1;i++)t[i].m1=t[i].v;
for(int i=N-1;i>=1;i--)merge(i);
}
signed main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
start();
for(int i=1;i<=m;i++)
{
//cout<<endl<<i<<":"<<endl;
//for(int j=1;j<=30;j++)cout<<t[j].v<<" "<<t[j].tag<<" "<<t[j].l0<<" "<<t[j].l1<<" "<<t[j].r0<<" "<<t[j].r1<<" "<<t[j].m0<<" "<<t[j].m1<<" "<<endl;
//cout<<endl;
cin>>a>>b>>c;
if(a==0)update(b+1,c+1,1,1);
if(a==1)update(b+1,c+1,2,1);
if(a==2)update(b+1,c+1,3,1);
if(a==3)cout<<query(b+1,c+1,1)<<endl;
if(a==4)cout<<query2(b+1,c+1,1).m1<<endl;
}
return 0;
}