dtbigwaves @ 2024-11-01 15:34:50
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long n,m,a[N],flag,ll,rr;
struct SegmentTree{
long long l,r,sum,lazy,rev,maxn[2],lmax[2],rmax[2];
}t[N*4];
void pushup(long long p){
t[p].sum=t[p*2].sum+t[p*2+1].sum;
for(long long i=0;i<=1;i++){
t[p].lmax[i]=t[p*2].lmax[i];
if(i==1 && t[p*2].sum==t[p*2].r-t[p*2].l+1) t[p].lmax[i]+=t[p*2+1].lmax[i];
else if(i==0 && t[p*2].sum==0) t[p].lmax[i]+=t[p*2+1].lmax[i];
t[p].rmax[i]=t[p*2+1].rmax[i];
if(i==1 && t[p*2+1].sum==t[p*2+1].r-t[p*2+1].l+1) t[p].rmax[i]+=t[p*2].rmax[i];
else if(i==0 && t[p*2+1].sum==0) t[p].rmax[i]+=t[p*2].rmax[i];
t[p].maxn[i]=t[p*2].rmax[i]+t[p*2+1].lmax[i];
t[p].maxn[i]=max(t[p].maxn[i],t[p*2].maxn[i]);
t[p].maxn[i]=max(t[p].maxn[i],t[p*2+1].maxn[i]);
}
}
void build(long long p,long long l,long long r){
t[p].l=l;
t[p].r=r;
t[p].lazy=-1;
if(l==r){
t[p].sum=a[l];
t[p].maxn[0]=t[p].lmax[0]=t[p].rmax[0]=a[l]==0;
t[p].maxn[1]=t[p].lmax[1]=t[p].rmax[1]=a[l]==1;
return;
}
long long mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
pushup(p);
}
void spread(long long p){
if(t[p].lazy!=-1){
t[p].rev=0;
long long val=t[p].lazy;
t[p*2].sum=(t[p*2].r-t[p*2].l+1)*val;
t[p*2+1].sum=(t[p*2+1].r-t[p*2+1].l+1)*val;
t[p*2].lazy=t[p*2+1].lazy=val;
t[p*2].rev=t[p*2+1].rev=0;
t[p*2].maxn[val]=t[p*2].lmax[val]=t[p*2].rmax[val]=t[p*2].r-t[p*2].l+1;
t[p*2].maxn[val^1]=t[p*2].lmax[val^1]=t[p*2].rmax[val^1]=0;
t[p*2+1].maxn[val]=t[p*2+1].lmax[val]=t[p*2+1].rmax[val]=t[p*2+1].r-t[p*2+1].l+1;
t[p*2+1].maxn[val^1]=t[p*2+1].lmax[val^1]=t[p*2+1].rmax[val^1]=0;
t[p].lazy=-1;
}
if(t[p].rev){
t[p*2].sum=(t[p*2].r-t[p*2].l+1)-t[p*2].sum;
t[p*2+1].sum=(t[p*2+1].r-t[p*2+1].l+1)-t[p*2+1].sum;
if(t[p*2].lazy!=-1) t[p*2].lazy^=1;
else t[p*2].rev^=1;
if(t[p*2+1].lazy!=-1) t[p*2+1].lazy^=1;
else t[p*2+1].rev^=1;
swap(t[p*2].maxn[0],t[p*2].maxn[1]);
swap(t[p*2].lmax[0],t[p*2].lmax[1]);
swap(t[p*2].rmax[0],t[p*2].rmax[1]);
swap(t[p*2+1].maxn[0],t[p*2+1].maxn[1]);
swap(t[p*2+1].lmax[0],t[p*2+1].lmax[1]);
swap(t[p*2+1].rmax[0],t[p*2+1].rmax[1]);
t[p].rev=0;
}
}
void cover(long long p,long long l,long long r){
spread(p);
if(t[p].l==l && t[p].r==r){
t[p].sum=(t[p].r-t[p].l+1)*flag;
t[p].lazy=flag;
t[p].maxn[flag]=t[p].lmax[flag]=t[p].rmax[flag]=t[p].r-t[p].l+1;
t[p].maxn[flag^1]=t[p].lmax[flag^1]=t[p].rmax[flag^1]=0;
return;
}
long long mid=(t[p].l+t[p].r)/2;
if(mid<l) cover(p*2+1,l,r);
else if(mid>=r) cover(p*2,l,r);
else{
cover(p*2,l,mid);
cover(p*2+1,mid+1,r);
}
pushup(p);
}
void rev(long long p,long long l,long long r){
spread(p);
if(t[p].l==l && t[p].r==r){
t[p].sum=(t[p].r-t[p].l+1)-t[p].sum;
t[p].rev^=1;
swap(t[p].maxn[0],t[p].maxn[1]);
swap(t[p].lmax[0],t[p].lmax[1]);
swap(t[p].rmax[0],t[p].rmax[1]);
return;
}
long long mid=(t[p].l+t[p].r)/2;
if(mid<l) rev(p*2+1,l,r);
else if(mid>=r) rev(p*2,l,r);
else{
rev(p*2,l,mid);
rev(p*2+1,mid+1,r);
}
pushup(p);
}
long long ask1(long long p,long long l,long long r){
spread(p);
if(t[p].l==l && t[p].r==r) return t[p].sum;
long long mid=(t[p].l+t[p].r)/2;
if(mid<l) return ask1(p*2+1,l,r);
else if(mid>=r) return ask1(p*2,l,r);
else return ask1(p*2,l,mid)+ask1(p*2+1,mid+1,r);
}
SegmentTree ask2(long long p,long long l,long long r){
spread(p);
if(t[p].l==l && t[p].r==r) return t[p];
long long mid=(t[p].l+t[p].r)/2;
if(mid<l) return ask2(p*2+1,l,r);
else if(mid>=r) return ask2(p*2,l,r);
else{
SegmentTree tot,lll=ask2(p*2,l,mid),rrr=ask2(p*2+1,mid+1,r);
tot.sum=lll.sum+rrr.sum;
for(long long i=0;i<=1;i++){
tot.lmax[i]=lll.lmax[i];
if(i==1 && lll.sum==lll.r-lll.l+1) tot.lmax[i]+=rrr.lmax[i];
else if(i==0 && lll.sum==0) tot.lmax[i]+=rrr.lmax[i];
tot.rmax[i]=rrr.rmax[i];
if(i==1 && rrr.sum==rrr.r-rrr.l+1) tot.rmax[i]+=lll.rmax[i];
else if(i==0 && rrr.sum==0) tot.rmax[i]+=lll.rmax[i];
tot.maxn[i]=lll.rmax[i]+lll.lmax[i];
tot.maxn[i]=max(tot.maxn[i],lll.maxn[i]);
tot.maxn[i]=max(tot.maxn[i],rrr.maxn[i]);
}
return tot;
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(long long i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
for(long long i=1;i<=m;i++){
cin>>flag>>ll>>rr;
ll++;
rr++;
if(flag==0 || flag==1) cover(1,ll,rr);
if(flag==2) rev(1,ll,rr);
if(flag==3) cout<<ask1(1,ll,rr)<<'\n';
if(flag==4) cout<<ask2(1,ll,rr).maxn[1]<<'\n';
}
return 0;
}