qnqfff @ 2022-07-16 12:43:38
代码放二楼
by qnqfff @ 2022-07-16 12:43:47
#include<bits/stdc++.h>
#define lson now<<1
#define rson now<<1|1
using namespace std;
inline int read(){
char ch=getchar();int s=0,f=1;
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),f=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return f*s;
}
int n,m;
struct node{
int l,r,sum,sumf,suml,w,tag1,tag2;
}t[400010],tt[400010];
void pushup(int now){
t[now].sum=t[lson].sum+t[rson].sum;
t[now].sumf=t[lson].sumf+(t[lson].sumf==t[lson].r-t[lson].l+1?t[rson].sumf:0);
t[now].suml=t[rson].suml+(t[rson].suml==t[rson].r-t[rson].l+1?t[lson].suml:0);
t[now].w=max(max(t[lson].w,t[rson].w),t[lson].suml+t[rson].sumf);
tt[now].sum=tt[lson].sum+tt[rson].sum;
tt[now].sumf=tt[lson].sumf+(tt[lson].sumf==t[lson].r-t[lson].l+1?tt[rson].sumf:0);
tt[now].suml=tt[rson].suml+(tt[rson].suml==t[rson].r-t[rson].l+1?tt[lson].suml:0);
tt[now].w=max(max(tt[lson].w,tt[rson].w),tt[lson].suml+tt[rson].sumf);
}
void build(int now,int l,int r){
t[now].l=l;t[now].r=r;t[now].tag1=-1;
if(l==r){
int x=read();
t[now].sum=t[now].sumf=t[now].suml=t[now].w=x;
tt[now].sum=tt[now].sumf=tt[now].suml=tt[now].w=!x;
return ;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(now);
}
void pushdown(int now){
if(t[now].tag1!=-1){
t[lson].tag2=t[rson].tag2=0;
t[lson].sum=t[lson].sumf=t[lson].suml=t[lson].w=t[now].tag1*(t[lson].r-t[lson].l+1);
t[rson].sum=t[rson].sumf=t[rson].suml=t[rson].w=t[now].tag1*(t[rson].r-t[rson].l+1);
t[lson].tag1=t[rson].tag1=t[now].tag1;
tt[lson].sum=tt[lson].sumf=tt[lson].suml=tt[lson].w=!t[now].tag1*(t[lson].r-t[lson].l+1);
tt[rson].sum=tt[rson].sumf=tt[rson].suml=tt[rson].w=!t[now].tag1*(t[rson].r-t[rson].l+1);
t[now].tag1=-1;
}
if(t[now].tag2){
swap(t[lson].sum,tt[lson].sum);
swap(t[lson].sumf,tt[lson].sumf);
swap(t[lson].suml,tt[lson].suml);
swap(t[lson].w,tt[lson].w);
swap(t[rson].sum,tt[rson].sum);
swap(t[rson].sumf,tt[rson].sumf);
swap(t[rson].suml,tt[rson].suml);
swap(t[rson].w,tt[rson].w);
t[lson].tag2=t[rson].tag2=t[now].tag2;
t[now].tag2=0;
}
}
void change1(int now,int l,int r,int v){
if(l<=t[now].l&&t[now].r<=r){
t[now].tag1=v;
t[now].tag2=0;
t[now].sum=t[now].sumf=t[now].suml=t[now].w=v*(t[now].r-t[now].l+1);
tt[now].sum=tt[now].sumf=tt[now].suml=tt[now].w=!v*(t[now].r-t[now].l+1);
return;
}
pushdown(now);
int mid=(t[now].l+t[now].r)>>1;
if(mid>=l)
change1(lson,l,r,v);
if(mid<r)
change1(rson,l,r,v);
pushup(now);
}
void change2(int now,int l,int r){
if(l<=t[now].l&&t[now].r<=r){
t[now].tag2^=1;
swap(t[now].sum,tt[now].sum);
swap(t[now].sumf,tt[now].sumf);
swap(t[now].suml,tt[now].suml);
swap(t[now].w,tt[now].w);
return ;
}
pushdown(now);
int mid=(t[now].l+t[now].r)>>1;
if(mid>=l)
change2(lson,l,r);
if(mid<r)
change2(rson,l,r);
pushup(now);
}
int query1(int now,int l,int r){
if(l<=t[now].l&&t[now].r<=r)
return t[now].sum;
pushdown(now);
int ans=0,mid=(t[now].l+t[now].r)>>1;
if(mid>=l)
ans+=query1(lson,l,r);
if(mid<r)
ans+=query1(rson,l,r);
return ans;
}
int query2(int now,int l,int r){
if(l<=t[now].l&&t[now].r<=r)
return t[now].w;
pushdown(now);
int ans=-1e9,mid=(t[now].l+t[now].r)>>1;
if(mid>=l)
ans=max(ans,query2(lson,l,r));
if(mid<r)
ans=max(ans,query2(rson,l,r));
if(l<=mid<r)
ans=max(ans,t[lson].suml-(mid-t[lson].suml+1>=l?0:l-(mid-t[lson].suml+1))+t[rson].sumf-(mid+t[rson].sumf<=r?0:(mid+t[rson].sumf)-r));
return ans;
}
int main(){
n=read();m=read();
build(1,1,n);
while(m--){
int opt=read(),l=read()+1,r=read()+1;
if(opt==0)
change1(1,l,r,0);
else if(opt==1)
change1(1,l,r,1);
else if(opt==2)
change2(1,l,r);
else if(opt==3)
cout<<query1(1,l,r)<<endl;
else
cout<<query2(1,l,r)<<endl;
}
return 0;
}