60分WA求调

P1253 扶苏的问题

qd_zhanghuali @ 2023-10-11 22:31:12

#include<cstdio>
#define ll long long
#define INF 21474836470000
ll tree[8000010],sca[1000010],tag[8000010],tag2[8000010],n,q,x,y,k;
inline ll maxx(ll a,ll b){
    if(a>b)return a;
    return b;
}
void build(ll p,ll l,ll r){
    tag2[p]=-INF;
    if(l==r){
        tree[p]=sca[l];
        return;
    }
    ll mid=(l+r-1)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    tree[p]=maxx(tree[p<<1],tree[p<<1|1]);
}
void change(ll p,ll l,ll r){
    if(x<=l&&r<=y){
        tag2[p]=k;
        tree[p]=k;
        return;
    }
    if(r<x||y<l)return;
    if(tag2[p]!=-INF){
        tree[p<<1]=tag2[p];
        tree[p<<1|1]=tag2[p];
        tag2[p<<1]=tag2[p];
        tag2[p<<1|1]=tag2[p];
        tag[p<<1]=0;
        tag[p<<1|1]=0;
        tag2[p]=-INF;
        tag[p]=0;
    }else{
        if(tag[p]!=0){// 
            tree[p<<1]+=tag[p];
            tree[p<<1|1]+=tag[p];
            tag[p<<1]+=tag[p];
            tag[p<<1|1]+=tag[p];
            tag[p]=0;
        }   
    }
    ll mid=(l+r-1)>>1;
    change(p<<1,l,mid);
    change(p<<1|1,mid+1,r);
    tree[p]=maxx(tree[p<<1],tree[p<<1|1]);
}
void add(ll p,ll l,ll r){
    if(x<=l&&r<=y){
        tree[p]+=k;
        tag[p]+=k;
        if(tag2[p]!=-INF)tag2[p]+=k;
        return;
    }
    if(y<l||x>r)return;
    if(tag2[p]!=-INF){
        tree[p<<1]=tag2[p];
        tree[p<<1|1]=tag2[p];
        tag2[p<<1]=tag2[p];
        tag2[p<<1|1]=tag2[p];
        tag[p<<1]=0;
        tag[p<<1|1]=0;
        tag2[p]=-INF;
        tag[p]=0;
    }else{
        if(tag[p]!=0){// 
            tree[p<<1]+=tag[p];
            tree[p<<1|1]+=tag[p];
            tag[p<<1]+=tag[p];
            tag[p<<1|1]+=tag[p];
            tag[p]=0;
        }   
    }
    ll mid=(l+r-1)>>1;
    add(p<<1,l,mid);
    add(p<<1|1,mid+1,r);
    tree[p]=maxx(tree[p<<1],tree[p<<1|1]);
}
ll ask(ll p,ll l,ll r){
    if(x<=l&&r<=y)return tree[p];
    if(y<l||x>r)return -INF;
    if(tag2[p]!=-INF){
        tree[p<<1]=tag2[p];
        tree[p<<1|1]=tag2[p];
        tag2[p<<1]=tag2[p];
        tag2[p<<1|1]=tag2[p];
        tag[p<<1]=0;
        tag[p<<1|1]=0;
        tag2[p]=-INF;
        tag[p]=0;
    }else{
        if(tag[p]!=0){// 
            tree[p<<1]+=tag[p];
            tree[p<<1|1]+=tag[p];
            tag[p<<1]+=tag[p];
            tag[p<<1|1]+=tag[p];
            tag[p]=0;
        }   
    }
    ll mid=(l+r-1)>>1;
    return maxx(ask(p<<1,l,mid),ask(p<<1|1,mid+1,r));
}
int main(){
    scanf("%lld %lld",&n,&q);
    ll i=0;
    for(i=1;i<=n;i++)scanf("%lld",&sca[i]);
    build(1,1,n);
    ll an=0;
    for(i=1;i<=q;i++){
        scanf("%lld %lld %lld",&an,&x,&y);
        if(an==3){//大 
            printf("%lld\n",ask(1,1,n));
        }else{
            scanf("%lld",&k);
            if(an==1){//改 
                change(1,1,n);
            }else{//2加 
                add(1,1,n);
            }
        }
    }
    return 0;
}

|