Judgelight @ 2022-08-17 14:59:24
#include<bits/stdc++.h>
#define int long long
#define N 100009
using namespace std;
int n,q,m,a,b,w[N];
struct Node{
int l,r,lmax[2],rmax[2],maxx[2],sum[2],bec,rev;
}tr[N*4];
void pushup(int u){
for(int i=0;i<=1;i++){
tr[u].sum[i]=tr[u<<1].sum[i]+tr[u<<1|1].sum[i];
}
for(int i=0;i<=1;i++){
tr[u].lmax[i]=max(tr[u<<1].lmax[i],tr[u<<1].sum[i]+tr[u<<1|1].lmax[i]);
tr[u].rmax[i]=max(tr[u<<1|1].rmax[i],tr[u<<1|1].sum[i]+tr[u<<1].rmax[i]);
tr[u].maxx[i]=max(tr[u].maxx[i],tr[u<<1].rmax[i]+tr[u<<1|1].lmax[i]);
}
}
void eval(Node &t,int bec,int rev){
if(bec!=-1){
t.rev=0,t.bec=bec;
t.sum[1]=(t.r-t.l+1)*bec;
t.sum[0]=(t.r-t.l+1)*(!bec);
t.maxx[bec]=t.lmax[bec]=t.rmax[bec]=t.r-t.l+1;
t.maxx[!bec]=t.lmax[!bec]=t.rmax[!bec]=0;
}
if(rev!=0){
if(t.bec!=-1){
t.bec=!t.bec;
}
else t.rev=!t.rev;
swap(t.sum[1],t.sum[0]);
swap(t.maxx[1],t.maxx[0]);
swap(t.lmax[1],t.lmax[0]);
swap(t.rmax[1],t.rmax[0]);
}
}
void pushdown(int u){
eval(tr[u<<1],tr[u].bec,tr[u].rev);
eval(tr[u<<1|1],tr[u].bec,tr[u].rev);
tr[u].bec=-1,tr[u].rev=0;
}
void build(int u,int l,int r){
tr[u].l=l,tr[u].r=r,tr[u].bec=-1,tr[u].rev=0;
if(l==r){
tr[u].lmax[1]=tr[u].rmax[1]=tr[u].maxx[1]=tr[u].sum[1]=w[l];
tr[u].lmax[0]=tr[u].rmax[0]=tr[u].maxx[0]=tr[u].sum[0]=!w[l];
return ;
}
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r,int x){
if(tr[u].l>=l&&tr[u].r<=r){
if(x==1||x==0){
eval(tr[u],x,0);
}
else eval(tr[u],-1,1);
return ;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l>mid){
modify(u<<1|1,l,r,x);
}
else if(r<=mid){
modify(u<<1,l,r,x);
}
else modify(u<<1,l,mid,x),modify(u<<1|1,mid+1,r,x);
pushup(u);
}
int query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){
return tr[u].sum[1];
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l>mid){
return query(u<<1|1,l,r);
}
else if(r<=mid){
return query(u<<1,l,r);
}
else return query(u<<1,l,mid)+query(u<<1|1,mid+1,r);
}
Node qmax(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){
return tr[u];
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l>mid){
return qmax(u<<1|1,l,r);
}
else if(r<=mid){
return qmax(u<<1,l,r);
}
else{
Node vex,left=qmax(u<<1,l,mid),right=qmax(u<<1|1,mid+1,r);
for(int i=0;i<=1;i++){
vex.sum[i]=left.sum[i]+right.sum[i];
vex.lmax[i]=max(left.lmax[i],left.sum[i]+right.lmax[i]);
vex.rmax[i]=max(right.rmax[i],right.sum[i]+left.rmax[i]);
vex.maxx[i]=left.rmax[i]+right.lmax[i];
}
return vex;
}
}
void Print(int u){
if(tr[u].l==tr[u].r){
cout<<tr[u].sum[1];
return ;
}
Print(u<<1);
Print(u<<1|1);
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>w[i];
}
build(1,1,n);
for(int i=1;i<=m;i++){
//Print(1);
//cout<<endl;
cin>>q>>a>>b;
a++,b++;
if(q==0||q==1||q==2){
modify(1,a,b,q);
}
else if(q==3){
cout<<query(1,a,b)<<endl;
}
else cout<<qmax(1,a,b).maxx[1]<<endl;
}
return 0;
}