likezheng2023 @ 2024-07-18 17:56:57
为什么加了142行就过了\ 不加就不过
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
register int x=0,f=0;register char c=getchar();
while(c<'0'||c>'9')f=(c=='-'),c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();
return f?-x:x;
}
const int MAXN=5e5;
int n,m,a[MAXN];
int la1[MAXN],an1[MAXN],ra1[MAXN],sum1[MAXN],la0[MAXN],ra0[MAXN],an0[MAXN],sum0[MAXN],ll[MAXN],rr[MAXN];
int fuz[MAXN],re[MAXN];
void pushup(int now){
int ls=now*2,rs=now*2+1;
ll[now]=ll[ls];rr[now]=rr[rs];
sum1[now]=sum1[ls]+sum1[rs];//sum0/1
sum0[now]=sum0[ls]+sum0[rs];
if(sum1[ls]==rr[ls]-ll[ls]+1)la1[now]=sum1[ls]+la1[rs];//la0/1
else la1[now]=la1[ls];
if(sum0[ls]==rr[ls]-ll[ls]+1)la0[now]=sum0[ls]+la0[rs];
else la0[now]=la0[ls];
if(sum1[rs]==rr[rs]-ll[rs]+1)ra1[now]=sum1[rs]+ra1[ls];//ra0/1
else ra1[now]=ra1[rs];
if(sum0[rs]==rr[rs]-ll[rs]+1)ra0[now]=sum0[rs]+ra0[ls];
else ra0[now]=ra0[rs];
an1[now]=max({an1[ls],an1[rs],ra1[ls]+la1[rs]});//an0/1
an0[now]=max({an0[ls],an0[rs],ra0[ls]+la0[rs]});
}
void pushdown(int now){
int ls=now*2,rs=now*2+1;
if(fuz[now]!=-1){
fuz[ls]=fuz[rs]=fuz[now];
re[ls]=re[rs]=0;
la1[ls]=ra1[ls]=an1[ls]=sum1[ls]=(fuz[now]==1)*(rr[ls]-ll[ls]+1);
la1[rs]=ra1[rs]=an1[rs]=sum1[rs]=(fuz[now]==1)*(rr[rs]-ll[rs]+1);
la0[ls]=ra0[ls]=an0[ls]=sum0[ls]=(fuz[now]==0)*(rr[ls]-ll[ls]+1);
la0[rs]=ra0[rs]=an0[rs]=sum0[rs]=(fuz[now]==0)*(rr[rs]-ll[rs]+1);
fuz[now]=-1;
}
if(re[now]){
if(fuz[ls]!=-1)fuz[ls]^=1;
if(fuz[rs]!=-1)fuz[rs]^=1;
re[ls]^=1;
re[rs]^=1;
swap(la1[ls],la0[ls]);swap(ra1[ls],ra0[ls]);swap(sum1[ls],sum0[ls]);swap(an1[ls],an0[ls]);
swap(la1[rs],la0[rs]);swap(ra1[rs],ra0[rs]);swap(sum1[rs],sum0[rs]);swap(an1[rs],an0[rs]);
re[now]=0;
}
}
void build(int cl=1,int cr=n,int p=1){
fuz[p]=-1;re[p]=0;
if(cl==cr){
ll[p]=rr[p]=cl;
la1[p]=an1[p]=ra1[p]=sum1[p]=(a[cl]==1);
la0[p]=an0[p]=ra0[p]=sum0[p]=(a[cl]==0);
return;
}
int mid=(cl+cr)>>1;
build(cl,mid,p*2),build(mid+1,cr,p*2+1);
pushup(p);
}
void fuzhi(int l,int r,int x,int cl=1,int cr=n,int p=1){
if(cr<l||cl>r||cl>cr)return;
if(l<=cl&&cr<=r){
fuz[p]=x;re[p]=0;
la1[p]=ra1[p]=sum1[p]=an1[p]=(x==1)*(cr-cl+1);
la0[p]=ra0[p]=sum0[p]=an0[p]=(x==0)*(cr-cl+1);
return;
}
int mid=(cl+cr)>>1;
pushdown(p);
fuzhi(l,r,x,cl,mid,p*2);fuzhi(l,r,x,mid+1,cr,p*2+1);
pushup(p);
}
void fanzhuan(int l,int r,int cl=1,int cr=n,int p=1){
if(cr<l||cl>r||cl>cr)return;
if(l<=cl&&cr<=r){
re[p]^=1;
if(fuz[p]!=-1)fuz[p]^=1;
swap(la1[p],la0[p]);swap(ra1[p],ra0[p]);swap(an1[p],an0[p]);swap(sum1[p],sum0[p]);
return;
}
int mid=(cl+cr)>>1;
pushdown(p);
fanzhuan(l,r,cl,mid,p*2);fanzhuan(l,r,mid+1,cr,p*2+1);
pushup(p);
}
int que1(int l,int r,int cl=1,int cr=n,int p=1){
if(cr<l||cl>r||cl>cr)return 0;
if(l<=cl&&cr<=r)return sum1[p];
int mid=(cl+cr)>>1;
pushdown(p);
return que1(l,r,cl,mid,p*2)+que1(l,r,mid+1,cr,p*2+1);
}
struct node{
int la1,la0,ra1,ra0,an1,an0,sum1,sum0,rr,ll;
}t;
node hb(node x,node y){
node res;
res.rr=y.rr;res.ll=x.ll;
res.sum1=x.sum1+y.sum1;//sum0/1
res.sum0=x.sum0+y.sum0;
if(x.sum1==x.rr-x.ll+1)res.la1=x.sum1+y.la1;//la0/1
else res.la1=x.la1;
if(x.sum0==x.rr-x.ll+1)res.la0=x.sum0+y.la0;
else res.la0=x.la0;
if(y.sum1==y.rr-y.ll+1)res.ra1=y.sum1+x.ra1;//ra0/1
else res.ra1=y.ra1;
if(y.sum0==y.rr-y.ll+1)res.ra0=y.sum0+x.ra0;
else res.ra0=y.ra0;
res.an1=max({x.an1,y.an1,x.ra1+y.la1});//an0/1
res.an0=max({x.an0,y.an0,x.ra0+y.la0});
return res;
}
node que2(int l,int r,int cl=1,int cr=n,int p=1){
if(cr<l||cl>r||cl>cr)return {0,0,0,0,0,0,0,0};
if(l<=cl&&cr<=r)return {la1[p],la0[p],ra1[p],ra0[p],an1[p],an0[p],sum1[p],sum0[p],cr,cl};
int mid=(cl+cr)>>1;
pushdown(p);
return hb(que2(l,r,cl,mid,p*2),que2(l,r,mid+1,cr,p*2+1));
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
build();
for(int i=1;i<=m;i++){
int op=read(),l=read(),r=read();
l++,r++;
if(op==0||op==1){
fuzhi(l,r,op);
// for(int j=1;j<=n;j++)que1(j,j);
}
else if(op==2){
fanzhuan(l,r);
}
else if(op==3){
cout<<que1(l,r)<<'\n';
}
else{
cout<<que2(l,r).an1<<'\n';
}
}
return 0;
}
by likezheng2023 @ 2024-07-18 18:01:21
到底是哪里没pushdown??????
by likezheng2023 @ 2024-07-18 18:30:23
自己找到了 已AC \ 此帖结
by Wilderness_ @ 2024-07-19 07:41:35
cjdl(不如平衡树)