zjr2014 @ 2024-12-16 10:22:36
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
int r=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')r=(r<<3)+(r<<1)+(c^48),c=getchar();
return r*f;
}
void file(string s){
s+=".in";
freopen(s.c_str(),"r",stdin);
s.pop_back();
s.pop_back();
s.pop_back();
s+=".out";
freopen(s.c_str(),"w",stdout);
}
void IOS(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int N=1e6+1;
struct segtree{
struct node{
int l,r;
int sum,sum0,sum1,charl,charr,sum0l,sum0r,sum1l,sum1r;
int add,set;
}t[N*4-3];
void pushup(int p){
t[p].sum=t[p*2].sum+t[p*2+1].sum;
t[p].sum0=max(t[p*2].sum0,t[p*2+1].sum0);
if(t[p*2].charr==t[p*2+1].charl){
t[p].sum0=max(t[p].sum0,t[p*2].sum0r+t[p*2+1].sum0l);
}
t[p].sum1=max(t[p*2].sum1,t[p*2+1].sum1);
if(t[p*2].charr==t[p*2+1].charl){
t[p].sum1=max(t[p].sum1,t[p*2].sum1r+t[p*2+1].sum1l);
}
t[p].sum0l=t[p*2].sum0l;
if(t[p*2].charr==t[p*2+1].charl){
if(t[p*2].sum0r==t[p*2].r-t[p*2].l+1){
t[p].sum0l=t[p*2].sum0r+t[p*2+1].sum0l;
}
}
t[p].sum1l=t[p*2].sum1l;
if(t[p*2].charr==t[p*2+1].charl){
if(t[p*2].sum1r==t[p*2].r-t[p*2].l+1){
t[p].sum1l=t[p*2].sum1r+t[p*2+1].sum1l;
}
}
t[p].sum0r=t[p*2+1].sum0r;
if(t[p*2].charr==t[p*2+1].charl){
if(t[p*2+1].sum0r==t[p*2+1].r-t[p*2+1].l+1){
t[p].sum0r=t[p*2+1].sum0r+t[p*2].sum0r;
}
}
t[p].sum1r=t[p*2+1].sum1r;
if(t[p*2].charr==t[p*2+1].charl){
if(t[p*2+1].sum1r==t[p*2+1].r-t[p*2+1].l+1){
t[p].sum1r=t[p*2+1].sum1r+t[p*2].sum1r;
}
}
t[p].charl=t[p*2].charl;
t[p].charr=t[p*2+1].charr;
}
void pushdown(int p){
if(t[p].add){
t[p*2].sum=(t[p*2].r-t[p*2].l+1)-t[p*2].sum;
t[p*2].charl^=1;
t[p*2].charr^=1;
swap(t[p*2].sum1,t[p*2].sum0);
swap(t[p*2].sum0l,t[p*2].sum1l);
swap(t[p*2].sum0r,t[p*2].sum1r);
t[p*2+1].sum=(t[p*2+1].r-t[p*2+1].l+1)-t[p*2+1].sum;
t[p*2+1].charl^=1;
t[p*2+1].charr^=1;
swap(t[p*2+1].sum1,t[p*2+1].sum0);
swap(t[p*2+1].sum0l,t[p*2+1].sum1l);
swap(t[p*2+1].sum0r,t[p*2+1].sum1r);
}
t[p*2].add^=t[p].add;
t[p*2+1].add^=t[p].add;
if(t[p].set){
t[p*2].set=t[p].set;
}
if(t[p].set){
t[p*2+1].set=t[p].set;
}
if(t[p].set==1){
t[p*2].sum=0;
t[p*2].sum1=0;
t[p*2].sum0=t[p*2].r-t[p*2].l+1;
t[p*2].charl=0;
t[p*2].charr=0;
t[p*2].sum1l=0;
t[p*2].sum0l=t[p*2].r-t[p*2].l+1;
t[p*2].sum1r=0;
t[p*2].sum0r=t[p*2].r-t[p*2].l+1;
t[p*2+1].sum=0;
t[p*2+1].sum1=0;
t[p*2+1].sum0=t[p*2+1].r-t[p*2+1].l+1;
t[p*2+1].charl=0;
t[p*2+1].charr=0;
t[p*2+1].sum1l=0;
t[p*2+1].sum0l=t[p*2+1].r-t[p*2+1].l+1;
t[p*2+1].sum1r=0;
t[p*2+1].sum0r=t[p*2+1].r-t[p*2+1].l+1;
}
if(t[p].set==2){
t[p*2].sum=t[p*2].r-t[p*2].l+1;
t[p*2].sum1=t[p*2].r-t[p*2].l+1;
t[p*2].sum0=0;
t[p*2].charl=1;
t[p*2].charr=1;
t[p*2].sum1l=t[p*2].r-t[p*2].l+1;
t[p*2].sum0l=0;
t[p*2].sum1r=t[p*2].r-t[p*2].l+1;
t[p*2].sum0r=0;
t[p*2+1].sum=t[p*2+1].r-t[p*2+1].l+1;
t[p*2+1].sum1=t[p*2+1].r-t[p*2+1].l+1;
t[p*2+1].sum0=0;
t[p*2+1].charl=1;
t[p*2+1].charr=1;
t[p*2+1].sum1l=t[p*2+1].r-t[p*2+1].l+1;
t[p*2+1].sum0l=0;
t[p*2+1].sum1r=t[p*2+1].r-t[p*2+1].l+1;
t[p*2+1].sum0r=0;
}
t[p].add=0;
t[p].set=0;
}
void build(int p,int l,int r,int a[]){
t[p].l=l;
t[p].r=r;
if(l==r){
t[p].sum=a[l];
t[p].sum0l=!a[l];
t[p].sum1l=a[l];
t[p].sum0r=!a[l];
t[p].sum1r=a[l];
t[p].sum0=!a[l];
t[p].sum1=a[l];
t[p].charl=a[l];
t[p].charr=a[l];
return;
}
build(p*2,l,(l+r)/2,a);
build(p*2+1,(l+r)/2+1,r,a);
pushup(p);
}
void update(int p,int l,int r){
if(t[p].l>=l&&t[p].r<=r){
if(!t[p].set){
t[p].add^=1;
}
else{
t[p].set=3-t[p].set;
}
t[p].sum=(t[p].r-t[p].l+1)-t[p].sum;
t[p].charl^=1;
t[p].charr^=1;
swap(t[p].sum1,t[p].sum0);
swap(t[p].sum0l,t[p].sum1l);
swap(t[p].sum0r,t[p].sum1r);
return;
}
int mid=(t[p].l+t[p].r)/2;
pushdown(p);
if(l<=mid){
update(p*2,l,r);
}
if(r>mid){
update(p*2+1,l,r);
}
pushup(p);
}
void update2(int p,int l,int r,int c){
if(t[p].l>=l&&t[p].r<=r){
t[p].add=0;
t[p].set=c+1;
if(t[p].set==1){
t[p].sum=0;
t[p].sum1=0;
t[p].sum0=t[p].r-t[p].l+1;
t[p].sum1l=0;
t[p].sum0l=t[p].r-t[p].l+1;
t[p].sum1r=0;
t[p].sum0r=t[p].r-t[p].l+1;
t[p].charl=0;
t[p].charr=0;
}
else{
t[p].sum=t[p].r-t[p].l+1;
t[p].sum1=t[p].r-t[p].l+1;
t[p].sum0=0;
t[p].sum1l=t[p].r-t[p].l+1;
t[p].sum0l=0;
t[p].sum1r=t[p].r-t[p].l+1;
t[p].sum0r=0;
t[p].charl=1;
t[p].charr=1;
}
return;
}
int mid=(t[p].l+t[p].r)/2;
pushdown(p);
if(l<=mid){
update2(p*2,l,r,c);
}
if(r>mid){
update2(p*2+1,l,r,c);
}
pushup(p);
}
int query(int p,int l,int r){
if(t[p].l>=l&&t[p].r<=r){
return t[p].sum;
}
int mid=(t[p].l+t[p].r)/2;
pushdown(p);
int ret=0;
if(l<=mid){
ret+=query(p*2,l,r);
}
if(r>mid){
ret+=query(p*2+1,l,r);
}
return ret;
}
int query2(int p,int l,int r){
if(t[p].l>=l&&t[p].r<=r){
return t[p].sum1;
}
int mid=(t[p].l+t[p].r)/2;
pushdown(p);
int ret=0;
if(l<=mid){
ret=query2(p*2,l,r);
}
if(r>mid){
int o=query2(p*2+1,l,r);
ret=max(ret,o);
if(t[p*2].charr==t[p*2+1].charl){
ret=max(ret,min(t[p*2].sum1r,t[p*2].r-l+1)+min(t[p*2+1].sum1l,r-t[p*2+1].l+1));
}
}
return ret;
}
}k;
int a[N],n,m,op,x,y;
signed main(){
IOS();
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
k.build(1,1,n,a);
for(int i=1;i<=m;i++){
cin>>op>>x>>y;
x++;
y++;
if(op==0){
k.update2(1,x,y,0);
}
else if(op==1){
k.update2(1,x,y,1);
}
else if(op==2){
k.update(1,x,y);
}
else if(op==3){
cout<<k.query(1,x,y)<<"\n";
}
else{
cout<<k.query2(1,x,y)<<"\n";
}
}
return 0;
}