zplqwq @ 2023-03-01 16:14:38
代码放2楼。
by zplqwq @ 2023-03-01 16:15:03
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
int w,b,lw,lb,rw,rb,mw,mb,l,r,len,add,add2;//add 区间反转 add2 区间赋值
// node(int w=0,int b=0,int lw=0,int lb=0,int rw=0,int rb=0,int mw=0,int mb=0,int l=0,int r=0,int len=0,int add=0,int add2=0):
// w(w),b(b),lw(lw),lb(lb),rw(rw),rb(rb),mw(mw),mb(mb),l(l),r(r),len(len),add(add),add2(add2){}
}t[N*4];
int n,m,a[N];
void out_put(int p){
cout<<p<<" "<<t[p].add<<" "<<t[p].w<<" "<<t[p].b<<" "<<t[p].lw<<" "<<t[p].lb<<" "<<t[p].rw<<" "<<t[p].rb<<" "<<t[p].mw<<" "<<t[p].mb<<endl;
}
void push_up(int p){
// if(p==4){
// out_put(8);out_put(9);
// }
t[p].w=t[p*2].w+t[p*2+1].w;t[p].b=t[p*2].b+t[p*2+1].b;
if(t[p*2].b==0) t[p].lw=(t[p*2].w+t[p*2+1].lw);
else t[p].lw=t[p*2].lw;
if(t[p*2].w==0) t[p].lb=(t[p*2].b+t[p*2+1].lb);
else t[p].lb=t[p*2].lb;
if(t[p*2+1].b==0) t[p].rw=(t[p*2].rw+t[p*2+1].w);
else t[p].rw=t[p*2+1].rw;
if(t[p*2+1].w==0) t[p].rb=(t[p*2].rb+t[p*2+1].b);
else t[p].rb=t[p*2+1].rb;
t[p].mw=max(max(t[p*2].mw,t[p*2+1].mw),t[p*2].rw+t[p*2+1].lw);
t[p].mb=max(max(t[p*2].mb,t[p*2+1].mb),t[p*2].rb+t[p*2+1].lb);
// if(p==2){cout<<"qwq ";out_put(p);out_put(p*2);out_put(p*4+1);}
}
void build(int l,int r,int p){
t[p].l=l;t[p].r=r;t[p].len=r-l+1;t[p].add2=-1;
if(l==r){
if(a[l]==0){
t[p].w=0;t[p].b=1;t[p].lw=0;t[p].lb=1;t[p].rw=0;t[p].rb=1;t[p].mw=0;t[p].mb=1;
}
else{
t[p].w=1;t[p].b=0;t[p].lw=1;t[p].lb=0;t[p].rw=1;t[p].rb=0;t[p].mw=1;t[p].mb=0;
}
return ;
}
int mid=(l+r)/2;
build(l,mid,p*2);build(mid+1,r,p*2+1);push_up(p);
}
void push_down(int p){
if(t[p].add2==0){//区间赋0
t[p*2].add2=0;t[p*2+1].add2=0;t[p*2].add=0;t[p*2+1].add=0;
t[p*2].w=0;t[p*2].lw=0;t[p*2].rw=0;t[p*2].mw=0;
t[p*2+1].w=0;t[p*2+1].lw=0;t[p*2+1].rw=0;t[p*2+1].mw=0;
t[p*2].b=t[p*2].len;t[p*2].lb=t[p*2].len;t[p*2].rb=t[p*2].len;t[p*2].mb=t[p*2].len;
t[p*2+1].b=t[p*2+1].len;t[p*2+1].lb=t[p*2+1].len;t[p*2+1].rb=t[p*2+1].len;t[p*2+1].mb=t[p*2+1].len;
t[p].add2=-1;
}
if(t[p].add2==1){//区间赋1
t[p*2].add2=1;t[p*2+1].add2=1;t[p*2].add=0;t[p*2+1].add=0;
t[p*2].w=t[p*2].len;t[p*2].lw=t[p*2].len;t[p*2].rw=t[p*2].len;t[p*2].mw=t[p*2].len;
t[p*2+1].w=t[p*2+1].len;t[p*2+1].lw=t[p*2+1].len;t[p*2+1].rw=t[p*2+1].len;t[p*2+1].mw=t[p*2+1].len;
t[p*2].b=0;t[p*2].lb=0;t[p*2].rb=0;t[p*2].mb=0;
t[p*2+1].b=0;t[p*2+1].lb=0;t[p*2+1].rb=0;t[p*2+1].mb=0;
t[p].add2=-1;
}
if(t[p].add!=0){//区间反转
t[p*2].add^=1;t[p*2+1].add^=1;
swap(t[p*2].w,t[p*2].b);swap(t[p*2].lw,t[p*2].lb);swap(t[p*2].rw,t[p*2].rb);swap(t[p*2].mw,t[p*2].mb);
swap(t[p*2+1].w,t[p*2+1].b);swap(t[p*2+1].lw,t[p*2+1].lb);swap(t[p*2+1].rw,t[p*2+1].rb);swap(t[p*2+1].mw,t[p*2+1].mb);
t[p].add=0;
}
}
void change(int l,int r,int p,int k){
if(l<=t[p].l and t[p].r<=r){
if(k==0){
t[p].add=0;
t[p].w=0;t[p].lw=0;t[p].rw=0;t[p].mw=0;
t[p].b=t[p].len;t[p].lb=t[p].len;t[p].rb=t[p].len;t[p].mb=t[p].len;
t[p].add2=0;
}
if(k==1){
t[p].add=0;
t[p].b=0;t[p].lb=0;t[p].rb=0;t[p].mb=0;
t[p].w=t[p].len;t[p].lw=t[p].len;t[p].rw=t[p].len;t[p].mw=t[p].len;
t[p].add2=1;
}
if(k==2){
swap(t[p].w,t[p].b);swap(t[p].lw,t[p].lb);swap(t[p].rw,t[p].rb);swap(t[p].mw,t[p].mb);
t[p].add^=1;
}
// cout<<k<<" "<<t[p].l<<" "<<t[p].r<<" "<<t[p].add<<endl;
// push_down(p);
// out_put(p);
// out_put(2);
return ;
}
int mid=(t[p].l+t[p].r)/2;
push_down(p);push_up(p);
if(l<=mid) change(l,r,p*2,k);
if(r>mid) change(l,r,p*2+1,k);
push_down(p);push_up(p);
}
node query(int l,int r,int p){
if(l<=t[p].l and t[p].r<=r) return t[p];
int mid=(t[p].l+t[p].r)/2;
push_up(p);push_down(p);
if(r<=mid) return query(l,r,p*2);
else if(l>mid) return query(l,r,p*2+1);
else{
node tmp=query(l,r,p*2);
node tmp2=query(l,r,p*2+1);
node ans;
ans.w=tmp.w+tmp2.w;
ans.b=tmp.b+tmp2.b;
if(tmp.b==0) ans.lw=(tmp.w+tmp2.lw);
else ans.lw=tmp.lw;
if(tmp.w==0) ans.lb=(tmp.b+tmp2.lb);
else ans.lb=tmp.lb;
if(tmp2.b==0) ans.rw=(tmp.rw+tmp2.w);
else ans.rw=tmp2.rw;
if(tmp2.w==0) ans.rb=(tmp.rb+tmp2.b);
else ans.rb=tmp2.rb;
ans.mw=max(max(tmp.mw,tmp2.mw),tmp.rw+tmp2.lw);
ans.mb=max(max(tmp.mb,tmp2.mb),tmp.rb+tmp2.lb);
push_up(p);
return ans;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,n,1);
while(m--){
int opt,l,r;cin>>opt>>l>>r;
l++;r++;
if(opt==0){
change(l,r,1,0);
}
if(opt==1){
change(l,r,1,1);
// cout<<t[2].w<<endl;
}
if(opt==2){
change(l,r,1,2);
}
else{
if(opt==3) cout<<query(l,r,1).w<<"\n";
else if(opt==4) cout<<query(l,r,1).mw<<"\n";
}
}
return 0;
}by rui_er @ 2023-03-01 16:40:20
@zplqwq 调过了，此贴终结