线段树20pts求调,WA on #1,#3,qwq

P1253 扶苏的问题

bitsetint @ 2023-05-11 21:38:14

Rt,代码:

#include <bits/stdc++.h>
using namespace std;
const long long nul=-1e18;
long long n,q;
long long a[1000010];
long long mx[4000010];
long long lz1[4000010];
long long lz2[4000010];
void pushdn1(long long pt){
    long long v1=pt*2;
    long long v2=pt*2+1;
    if(lz1[pt]!=nul)
        lz1[v1]=lz1[v2]=mx[v1]=mx[v2]=lz1[pt];
    lz2[v1]=lz2[v2]=lz2[pt]=0;
    lz1[v1]=nul;
}
void pushdn2(long long pt){
    long long v1=pt*2;
    long long v2=pt*2+1;
    if(lz1[v1]!=nul&&lz1[v2]!=nul){
        lz1[v1]+=lz2[pt];
        lz1[v2]+=lz2[pt];
    }else{
        lz2[v1]+=lz2[pt];
        lz2[v2]+=lz2[pt];
    }
    lz2[pt]=0;
}
void build(long long l,long long r,long long pt){
    if(l==r){
        mx[pt]=a[l];
        return ;
    }
    long long mid=(l+r)/2;
    build(l,mid,pt*2);
    build(mid+1,r,pt*2+1);
    mx[pt]=max(mx[pt*2],mx[pt*2+1]);
//  cout<<l<<" "<<r<<" "<<mx[pt*2]<<" "<<mx[pt*2+1]<<endl;
}
void oprat1(long long l,long long r,long long nl,long long nr,long long pt,long long val){
    if(l>=nl&&r<=nr){
        lz1[pt]=val;
        mx[pt]=val;
        lz2[pt]=0;
        return ;
    }
    if(l>nr||r<nl){
        return ;
    }
    if(lz1[pt]!=nul)
    pushdn1(pt);
    else
    pushdn2(pt);
    long long mid=(l+r)/2;
    oprat1(l,mid,nl,nr,pt*2,val);
    oprat1(mid+1,r,nl,nr,pt*2+1,val);
    mx[pt]=max(mx[pt*2],mx[pt*2+1]);
}
void oprat2(long long l,long long r,long long nl,long long nr,long long pt,long long val){
    if(l>=nl&&r<=nr){
        if(lz1[pt]==nul){
            lz2[pt]+=val;
        }else{
            lz1[pt]+=val;
        }
        mx[pt]+=val;
        return ;
    }
    if(l>nr||r<nl){
        return ;
    }
    if(lz1[pt]!=nul)
    pushdn1(pt);
    else
    pushdn2(pt);
    long long mid=(l+r)/2;
    oprat2(l,mid,nl,nr,pt*2,val);
    oprat2(mid+1,r,nl,nr,pt*2+1,val);
    mx[pt]=max(mx[pt*2],mx[pt*2+1]);
}
long long ans=0;
void solve(long long l,long long r,long long nl,long long nr,long long pt){
//  cout<<l<<" "<<r<<endl;
    if(l>=nl&&r<=nr){
        ans=max(ans,mx[pt]);
        return ;
    }
    if(l>nr||r<nl){
        return ;
    }
    if(lz1[pt]!=nul)
    pushdn1(pt);
    else
    pushdn2(pt);
    long long mid=(l+r)/2;
    solve(l,mid,nl,nr,pt*2);
    solve(mid+1,r,nl,nr,pt*2+1);
}
int main(){
    scanf("%lld%lld",&n,&q);
    for(long long i=0;i<n*4+5;i++){
        lz1[i]=nul;
    }
    for(long long i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    build(1,n,1);
    while(q--){
        long long op;
        scanf("%lld",&op);
        if(op==1){
            long long l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            oprat1(1,n,l,r,1,x);
        }else if(op==2){
            long long l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            oprat2(1,n,l,r,1,x);
        }else{
            long long l,r;
            scanf("%lld%lld",&l,&r);
            ans=nul;
            solve(1,n,l,r,1);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

by WELTh1113 @ 2023-05-11 21:39:31

这这这


by bitsetint @ 2023-05-11 21:40:15

@WELTh1113 ?


by __xzm__ @ 2023-05-11 22:31:24

@yxq666 \ 应该是懒标记维护的有问题。\ 我之前20pts 和你一样的错误,就是懒标记维护的时候用lazy2去更新了lazy1。\ 后来改了lazy\_tag的更新方式,定义lazy1的优先级高于lazy2的优先级,就是push\_down的时候先去push\_tag lazy1就行了AC


by bitsetint @ 2023-05-12 18:58:04

@xzm 我每次pushdown的时候是先 push_tag lazy1 了吧(?


|