样例没过,求助

P2572 [SCOI2010] 序列操作

Judgelight @ 2022-08-17 14:59:24

#include<bits/stdc++.h>
#define int long long
#define N 100009
using namespace std;
int n,q,m,a,b,w[N];
struct Node{
    int l,r,lmax[2],rmax[2],maxx[2],sum[2],bec,rev;
}tr[N*4];
void pushup(int u){
    for(int i=0;i<=1;i++){
        tr[u].sum[i]=tr[u<<1].sum[i]+tr[u<<1|1].sum[i];
    }
    for(int i=0;i<=1;i++){
        tr[u].lmax[i]=max(tr[u<<1].lmax[i],tr[u<<1].sum[i]+tr[u<<1|1].lmax[i]);
        tr[u].rmax[i]=max(tr[u<<1|1].rmax[i],tr[u<<1|1].sum[i]+tr[u<<1].rmax[i]);
        tr[u].maxx[i]=max(tr[u].maxx[i],tr[u<<1].rmax[i]+tr[u<<1|1].lmax[i]);
    }
}
void eval(Node &t,int bec,int rev){
    if(bec!=-1){
        t.rev=0,t.bec=bec;
        t.sum[1]=(t.r-t.l+1)*bec;
        t.sum[0]=(t.r-t.l+1)*(!bec);
        t.maxx[bec]=t.lmax[bec]=t.rmax[bec]=t.r-t.l+1;
        t.maxx[!bec]=t.lmax[!bec]=t.rmax[!bec]=0;
    }
    if(rev!=0){
        if(t.bec!=-1){
            t.bec=!t.bec;
        }
        else t.rev=!t.rev;
        swap(t.sum[1],t.sum[0]);
        swap(t.maxx[1],t.maxx[0]);
        swap(t.lmax[1],t.lmax[0]);
        swap(t.rmax[1],t.rmax[0]);
    }
}
void pushdown(int u){
    eval(tr[u<<1],tr[u].bec,tr[u].rev);
    eval(tr[u<<1|1],tr[u].bec,tr[u].rev);
    tr[u].bec=-1,tr[u].rev=0;
}
void build(int u,int l,int r){
    tr[u].l=l,tr[u].r=r,tr[u].bec=-1,tr[u].rev=0;
    if(l==r){
        tr[u].lmax[1]=tr[u].rmax[1]=tr[u].maxx[1]=tr[u].sum[1]=w[l];
        tr[u].lmax[0]=tr[u].rmax[0]=tr[u].maxx[0]=tr[u].sum[0]=!w[l];
        return ;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void modify(int u,int l,int r,int x){
    if(tr[u].l>=l&&tr[u].r<=r){
        if(x==1||x==0){
            eval(tr[u],x,0);
        }
        else eval(tr[u],-1,1);
        return ;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l>mid){
        modify(u<<1|1,l,r,x);
    }
    else if(r<=mid){
        modify(u<<1,l,r,x);
    }
    else modify(u<<1,l,mid,x),modify(u<<1|1,mid+1,r,x);
    pushup(u);
}
int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r){
        return tr[u].sum[1];
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l>mid){
        return query(u<<1|1,l,r);
    }
    else if(r<=mid){
        return query(u<<1,l,r);
    }
    else return query(u<<1,l,mid)+query(u<<1|1,mid+1,r);
}
Node qmax(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r){
        return tr[u];
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l>mid){
        return qmax(u<<1|1,l,r);
    }
    else if(r<=mid){
        return qmax(u<<1,l,r);
    }
    else{
        Node vex,left=qmax(u<<1,l,mid),right=qmax(u<<1|1,mid+1,r);
        for(int i=0;i<=1;i++){
            vex.sum[i]=left.sum[i]+right.sum[i];
            vex.lmax[i]=max(left.lmax[i],left.sum[i]+right.lmax[i]);
            vex.rmax[i]=max(right.rmax[i],right.sum[i]+left.rmax[i]);
            vex.maxx[i]=left.rmax[i]+right.lmax[i];
        }
        return vex;
    }
}
void Print(int u){
    if(tr[u].l==tr[u].r){
        cout<<tr[u].sum[1];
        return ;
    }
    Print(u<<1);
    Print(u<<1|1);
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        //Print(1);
        //cout<<endl;
        cin>>q>>a>>b;
        a++,b++;
        if(q==0||q==1||q==2){
            modify(1,a,b,q);
        }
        else if(q==3){
            cout<<query(1,a,b)<<endl;
        }
        else cout<<qmax(1,a,b).maxx[1]<<endl;
    }
    return 0;
}

|