dubnium @ 2024-01-31 23:23:58
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+6,INF=1e5;
struct Segment_tree {
int l,r,tag[2],sum[4],maxl[2],maxr[2],dat[2];
} T[maxn<<2];
int n,m;
int num[maxn];
void spread(int p) {
if(~T[p].tag[0]) {
int t=T[p].tag[0];
if(t)
T[p<<1].sum[2]=(T[p<<1].r-T[p<<1].l+1),T[p<<1|1].sum[2]=(T[p<<1|1].r-T[p<<1|1].l+1);
else T[p<<1].sum[2]=T[p<<1|1].sum[2]=0;
if(!t)
T[p<<1].sum[3]=(T[p<<1].r-T[p<<1].l+1),T[p<<1|1].sum[3]=(T[p<<1|1].r-T[p<<1|1].l+1);
else T[p<<1].sum[3]=T[p<<1|1].sum[3]=0;
T[p<<1].sum[!t]=T[p<<1].maxl[!t]=T[p<<1].maxr[!t]=T[p<<1].dat[!t]=0;
T[p<<1].sum[t]=T[p<<1].maxl[t]=T[p<<1].maxr[t]=T[p<<1].dat[t]=(T[p<<1].r-T[p<<1].l+1);
T[p<<1|1].sum[!t]=T[p<<1|1].maxl[!t]=T[p<<1|1].maxr[!t]=T[p<<1|1].dat[!t]=0;
T[p<<1|1].sum[t]=T[p<<1|1].maxl[t]=T[p<<1|1].maxr[t]=T[p<<1|1].dat[t]=(T[p<<1|1].r-T[p<<1|1].l+1);
T[p<<1].tag[0]=T[p<<1|1].tag[0]=T[p].tag[0],T[p].tag[0]=-1;
}
if(T[p].tag[1]) {
swap(T[p<<1].sum[0],T[p<<1].sum[1]),swap(T[p<<1].maxl[0],T[p<<1].maxl[1]),swap(T[p<<1].maxr[0],T[p<<1].maxr[1]),swap(T[p<<1].dat[0],T[p<<1].dat[1]);
swap(T[p<<1|1].sum[0],T[p<<1|1].sum[1]),swap(T[p<<1|1].maxl[0],T[p<<1|1].maxl[1]),swap(T[p<<1|1].maxr[0],T[p<<1|1].maxr[1]),swap(T[p<<1|1].dat[0],T[p<<1|1].dat[1]);
swap(T[p<<1].sum[2],T[p<<1].sum[3]),swap(T[p<<1|1].sum[2],T[p<<1|1].sum[3]);
T[p<<1].tag[1]=T[p<<1|1].tag[1]=T[p].tag[1],T[p].tag[1]=0;
}
}
void pushup(int p) {
T[p].sum[0]=T[p<<1].sum[0]+T[p<<1|1].sum[0];
T[p].sum[1]=T[p<<1].sum[1]+T[p<<1|1].sum[1];
T[p].sum[2]=T[p<<1].sum[2]+T[p<<1|1].sum[2];
T[p].sum[3]=T[p<<1].sum[3]+T[p<<1|1].sum[3];
T[p].maxl[0]=max(T[p<<1].maxl[0],T[p<<1].sum[0]+T[p<<1|1].maxl[0]);
T[p].maxl[1]=max(T[p<<1].maxl[1],T[p<<1].sum[1]+T[p<<1|1].maxl[1]);
T[p].maxr[0]=max(T[p<<1|1].maxr[0],T[p<<1|1].sum[0]+T[p<<1].maxr[0]);
T[p].maxr[1]=max(T[p<<1|1].maxr[1],T[p<<1|1].sum[1]+T[p<<1].maxr[1]);
T[p].dat[0]=max({T[p<<1].dat[0],T[p<<1|1].dat[0],T[p<<1].maxr[0]+T[p<<1|1].maxl[0]});
T[p].dat[1]=max({T[p<<1].dat[1],T[p<<1|1].dat[1],T[p<<1].maxr[1]+T[p<<1|1].maxl[1]});
}
void Build(int p,int l,int r) {
T[p].l=l,T[p].r=r;
if(l==r) {
if(num[l])
T[p]= {T[p].l,T[p].r,-1,0,-INF,1,1,0,-INF,1,-INF,1,-INF,1};
if(!num[l])
T[p]= {T[p].l,T[p].r,-1,0,1,-INF,0,1,1,-INF,1,-INF,1,-INF};
return ;
}
int mid=l+r>>1;
Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
pushup(p);
}
void change(int p,int x,int y,int t) {
if(x<=T[p].l&&T[p].r<=y) {
if(t==2) {
swap(T[p].sum[0],T[p].sum[1]),swap(T[p].maxl[0],T[p].maxl[1]),swap(T[p].maxr[0],T[p].maxr[1]),swap(T[p].dat[0],T[p].dat[1]);
swap(T[p].sum[2],T[p].sum[3]);
T[p].tag[1]=1;
} else {
T[p].sum[!t]=T[p].maxl[!t]=T[p].maxr[!t]=T[p].dat[!t]=0;
T[p].sum[t]=T[p].maxl[t]=T[p].maxr[t]=T[p].dat[t]=(T[p].r-T[p].l+1);
if(t)
T[p].sum[2]=(T[p].r-T[p].l+1);
else T[p].sum[2]=0;
if(!t)
T[p].sum[3]=(T[p].r-T[p].l+1);
else T[p].sum[3]=0;
T[p].tag[0]=t;
}
return ;
}
spread(p);
int mid=T[p].l+T[p].r>>1;
if(x<=mid)
change(p<<1,x,y,t);
if(y>mid)
change(p<<1|1,x,y,t);
pushup(p);
}
Segment_tree query(int p,int x,int y) {
if(x<=T[p].l&&T[p].r<=y)
return T[p];
spread(p);
int mid=T[p].l+T[p].r>>1;
Segment_tree a,b,res;
if(x<=mid)
a=query(p<<1,x,y);
if(y>mid)
b=query(p<<1|1,x,y);
res.sum[0]=a.sum[0]+b.sum[0];
res.sum[1]=a.sum[1]+b.sum[1];
res.sum[2]=a.sum[2]+b.sum[2];
res.sum[3]=a.sum[3]+b.sum[3];
res.maxl[0]=max(a.maxl[0],a.sum[0]+b.maxl[0]);
res.maxr[0]=max(b.maxr[0],b.sum[0]+a.maxr[0]);
res.maxr[1]=max(b.maxr[1],b.sum[1]+a.maxr[1]);
res.maxl[1]=max(a.maxl[1],a.sum[1]+b.maxl[1]);
res.dat[0]=max({a.dat[0],b.dat[0],a.maxr[0]+b.maxl[0]});
res.dat[1]=max({a.dat[1],b.dat[1],a.maxr[1]+b.maxl[1]});
return res;
}
int ask(int p,int x,int y) {
if(x<=T[p].l&&T[p].r<=y)
return T[p].sum[2];
spread(p);
int mid=T[p].l+T[p].r>>1,res=0;
if(x<=mid)
res+=ask(p<<1,x,y);
if(y>mid)
res+=ask(p<<1|1,x,y);
return res;
}
signed main() {
scanf("%lld%lld",&n,&m);
for(int i=1; i<=n; i++)
scanf("%lld",&num[i]);
Build(1,1,n);
int op,l,r;
while(m--) {
scanf("%lld%lld%lld",&op,&l,&r);
l++,r++;
if(op<=2)
change(1,l,r,op);
else if(op==3)
printf("%lld\n",ask(1,l,r));
else
printf("%lld\n",query(1,l,r).dat[1]);
}
return 0;
}