liuziqin @ 2023-08-26 12:34:28
#include<bits/stdc++.h>
using namespace std;
const int N=400000;
struct node{
int lm,rm,sum,all;
};
int sum[N][2],size[N],lazy[N],a[N>>2],lm[N][2],rm[N][2],all[N][2];
bool mark1[N],mark2[N];
void pushup(int p){
sum[p][0]=sum[p*2][0]+sum[p*2+1][0];
sum[p][1]=sum[p*2][1]+sum[p*2+1][1];
lm[p][0]=lm[p*2][0];
lm[p][1]=lm[p*2][1];
rm[p][0]=rm[p*2+1][0];
rm[p][1]=rm[p*2+1][1];
if(lm[p*2][0]==size[p*2])lm[p][0]+=lm[p*2+1][0];
if(lm[p*2][1]==size[p*2])lm[p][1]+=lm[p*2+1][1];
if(rm[p*2+1][0]==size[p*2+1])rm[p][0]+=rm[p*2][0];
if(rm[p*2+1][1]==size[p*2+1])rm[p][1]+=rm[p*2][1];
all[p][0]=max(max(all[p*2][0],all[p*2+1][0]),lm[p*2+1][0]+rm[p*2][0]);
all[p][1]=max(max(all[p*2][1],all[p*2+1][1]),lm[p*2+1][1]+rm[p*2][1]);
size[p]=size[p*2]+size[p*2+1];
}
void build(int p,int l,int r){
mark1[p]=mark2[p]=0;
if(l==r){
sum[p][a[l]]=1;
lm[p][a[l]]=1;
rm[p][a[l]]=1;
all[p][a[l]]=1;
size[p]=1;
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
pushup(p);
}
void a_lazy1(int p,int v){
lm[p][v]=size[p];
rm[p][v]=size[p];
all[p][v]=size[p];
sum[p][v]=size[p];
lazy[p]=v;
if(v==1)v=0;else v=1;
sum[p][v]=lm[p][v]=rm[p][v]=all[p][v]=0;
mark1[p]=1;
}
void push_down1(int p){
if(!mark1[p])return;
a_lazy1(p*2,lazy[p]);
a_lazy1(p*2+1,lazy[p]);
lazy[p]=0;
mark1[p]=0;
}
void a_lazy2(int p){
swap(lm[p][1],lm[p][0]);
swap(rm[p][0],rm[p][1]);
swap(sum[p][0],sum[p][1]);
swap(all[p][0],all[p][1]);
mark2[p]=1;
}
void push_down2(int p){
if(!mark2[p])return;
a_lazy2(p*2);
a_lazy2(p*2+1);
mark2[p]=0;
}
void push_down(int p){
push_down1(p);
push_down2(p);
}
void add(int p,int l,int r,int x,int y,int v){
if(l>=x&&r<=y){
a_lazy1(p,v);
return;
}
int mid=(l+r)/2;
push_down(p);
if(mid>=x)add(p*2,l,mid,x,y,v);
if(mid<y)add(p*2+1,mid+1,r,x,y,v);
pushup(p);
}
void change(int p,int l,int r,int x,int y){
if(l>=x&&r<=y){
a_lazy2(p);
return;
}
int mid=(l+r)/2;
push_down(p);
if(mid>=x)change(p*2,l,mid,x,y);
if(mid<y)change(p*2+1,mid+1,r,x,y);
pushup(p);
}
int query1(int p,int l,int r,int x,int y){
if(l>=x&&r<=y)return sum[p][1];
int mid=(l+r)/2,ans=0;
push_down(p);
if(mid>=x)ans+=query1(p*2,l,mid,x,y);
if(mid<y)ans+=query1(p*2+1,mid+1,r,x,y);
return ans;
}
node query(int p,int l,int r,int x,int y){
if(l>=x&&r<=y){
node ans;
ans.lm=lm[p][1],ans.rm=rm[p][1],ans.sum=sum[p][1],ans.all=all[p][1];
return ans;
}
int mid=(l+r)/2;
push_down(p);
node ans1,ans2;
bool p1,p2;
if(mid>=x)ans1=query(p*2,l,mid,x,y),p1=1;
if(mid<y)ans2=query(p*2+1,mid+1,r,x,y),p2=1;
if(p1)return ans1;
if(p2)return ans2;
if(p1&&p2){
node res;
res.lm=ans1.lm;
if(ans1.lm==size[p*2])res.lm+=ans2.lm;
res.rm=ans2.rm;
if(ans2.rm==size[p*2+1])res.rm+=ans1.rm;
res.sum=ans1.sum+ans2.sum;
res.all=max(max(ans1.all,ans2.all),ans1.rm+ans2.lm);
return res;
}
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
while(m--){
int op,x,y;
cin>>op>>x>>y;
if(x>y)swap(x,y);
x++,y++;
if(op==0)add(1,1,n,x,y,0);
if(op==1)add(1,1,n,x,y,1);
if(op==2)change(1,1,n,x,y);
if(op==3)cout<<query1(1,1,n,x,y)<<endl;
if(op==4)cout<<query(1,1,n,x,y).all<<endl;
}
}