求助!!!!

P1253 扶苏的问题

AC_AC_AC @ 2024-03-21 21:54:32

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10,N=-1e9-10;
int a[maxn],sum[maxn<<2],tagA[maxn<<2],tagP[maxn<<2];
int sl(int rt){
    return rt<<1;
}
int sl2(int rt){
    return rt<<1|1;
}
void Push_Up(int rt){
    sum[rt] = max(sum[sl(rt)],sum[sl2(rt)]);
}
void BuildTree(int rt,int l,int r){
    tagA[rt] = N;
    if(l == r){
        sum[rt] = a[l];
        return;
    }
    int mid = (l+r)>>1;
    BuildTree(sl(rt),l,mid);
    BuildTree(sl2(rt),mid+1,r);
    Push_Up(rt);
}
void lazytagA(int rt,int d){//xiugai
    tagA[rt] = d;
    sum[rt] = d;
    tagP[rt] =d;
}
void lazytagP(int rt,int d){//jia
    tagP[rt] +=d;
    sum[rt] +=d;
}
void pushdownA(int rt){//xiugai
    if(sum[rt] != N){
        lazytagA(sl(rt),tagA[rt]);
        lazytagA(sl2(rt),tagA[rt]);
    }
    tagA[rt] = N;
}
void pushdownB(int rt){//jia
    if(tagP[rt]){
        lazytagP(sl(rt),tagP[rt]);
        lazytagP(sl2(rt),tagP[rt]);
    }
    tagP[rt] = 0;
}
void updateA(int rt,int l,int r,int L,int R,int d){//xiuagi
    if(L<=l && R>=r){
        lazytagA(rt,d);
        return;
    }
    pushdownA(rt);
    pushdownB(rt);
    int mid = (l+r)>>1;
    if(l<=mid){
        updateA(rt<<1,l,mid,L,R,d);
    }
    if(R>mid){
        updateA(rt<<1|1,mid+1,r,L,R,d);
    }
    Push_Up(rt);
}
void updateP(int rt,int l,int r,int L,int R,int d){//jia
    if(L<=l && R>=r){
        lazytagP(rt,d);
        return;
    }
    pushdownA(rt);
    pushdownB(rt);
    int mid=(l+r)>>1;
    if(L<=mid)
        updateP(rt<<1,l,mid,L,R,d);
    if(R>mid)
        updateP(rt<<1|1,mid+1,r,L,R,d);
    Push_Up(rt);
}
int ask(int rt,int l,int r,int L,int R){
    if(L<=l && R<=r){
        return sum[rt];
    }
    pushdownA(rt);
    pushdownB(rt);
    int LLRR=-114514514;
    int mid = (l+r)>>1;
    if(L<=mid) LLRR = max(LLRR,ask(rt<<1,l,mid,L,R));
    if(R>mid) LLRR = max(LLRR,ask(rt<<1|1,mid+1,r,L,R));
    return LLRR;
}
int main(){
    int n,m,op=0,l,r,d;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    BuildTree(1,1,n);
    for(int i=1;i<=m;++i){
        scanf("%d",&op);
        if(op == 1){
            scanf("%d%d%d",&l,&r,&d);
            updateA(1,1,n,l,r,d);
        }
        if(op == 2){
            scanf("%d%d%d",&l,&r,&d);
            updateP(1,1,n,l,r,d);
        }
        if(op == 3){
            scanf("%d%d",&l,&r);
            printf("%d\n",ask(1,1,n,l,r));
        }
    }
    return 0;
}

by LK_LZTL @ 2024-04-22 17:35:25

tagP[rt] =d;改为tagP[rt] = 0; sum[rt] != N改为tagA[rt] != N ; R<=r改为R>=r ...... 等等


|