为什么加了一句话就过了

P2572 [SCOI2010] 序列操作

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(不如平衡树)


|