样例过了,提交20分,求调

P1253 扶苏的问题

膜拜陈桉大佬 @ 2022-11-24 14:14:06

自己调了好久,成功地把RE调成了WA。。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll n;
ll a[1000020];
struct node{
    ll l,r,lz,mx,sl;
}tree[4000020];
void build (ll k,ll l,ll r){
    tree[k].l=l;
    tree[k].r=r;
    tree[k].lz=0;
    tree[k].sl=0;
    if(l==r){
        tree[k].mx=a[l];
        return;
    }
    ll mid,lc,rc;
    lc=2*k;
    rc=2*k+1;
    mid=l+(r-l)/2;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tree[k].mx=max(tree[lc].mx,tree[rc].mx);
}
void lazy(ll k,ll v){
    tree[k].mx=v;
    tree[k].lz=v;
    tree[k].sl=0;
}
void pushdown(ll k){
    lazy(2*k,tree[k].lz);
    lazy(2*k+1,tree[k].lz);
    tree[k].lz=0;
}
void p_pushdown(ll k){
    ll mid,lc,rc;
    lc=2*k;
    rc=2*k+1;
    mid=(tree[k].l+tree[k].r)/2;
    tree[lc].sl+=tree[k].sl;
    tree[rc].sl+=tree[k].sl;
    tree[k].sl=0;
}
void update(ll k,ll l,ll r,ll v){
    if(tree[k].l>=l&&tree[k].r<=r){
        lazy(k,v);
        pushdown(k);
        return;

    }
    if(tree[k].lz!=0)pushdown(k);
    ll mid,lc,rc;
    lc=2*k;
    rc=2*k+1;
    mid=(tree[k].l+tree[k].r)/2;
    if(l<=mid)update(lc,l,r,v);
    if(r>mid)update(rc,l,r,v);
    tree[k].mx=max(tree[lc].mx,tree[rc].mx);

}
void p_update(ll k,ll l,ll  r,ll v){
    if(tree[k].l>=l&&tree[k].r<=r){
        tree[k].mx+=v;
        if(tree[k].lz!=0)tree[k].lz+=v;
        else tree[k].sl+=v;
        p_pushdown(k);
        return;
    }
    if(tree[k].lz!=0)pushdown(k);
    if(tree[k].sl!=0)p_pushdown(k);
    ll mid,lc,rc;
    lc=2*k;
    rc=2*k+1;
    mid=tree[k].l+(tree[k].r-tree[k].l)/2;
    if(l<=mid)p_update(lc,l,r,v);
    if(r>mid)p_update(rc,l,r,v);
    tree[k].mx=max(tree[lc].mx,tree[rc].mx);

}
ll query(ll k,ll l,ll r){
    if(tree[k].l>=l&&tree[k].r<=r){
        return tree[k].mx;
    }
    if(tree[k].lz!=0)pushdown(k);
    ll maxx=-1e15-1;
    ll mid,lc,rc;
    lc=2*k;
    rc=2*k+1;
    mid=(tree[k].l+tree[k].r)/2;
    if(l<=mid)maxx=max(maxx,query(lc,l,r));
    if(r>mid)maxx=max(maxx,query(rc,l,r));
    return maxx;
}
int main(){
    ll q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    build(1,1,n);
    for(int i=1;i<=q;i++){
        int op;
        ll l,r,x;
        cin>>op;
        if(op==1){
            cin>>l>>r>>x;
            update(1,l,r,x);
        }
        else if(op==2){
            cin>>l>>r>>x;
            p_update(1,l,r,x);
        }
        else if(op==3){
            cin>>l>>r;
            cout<<query(1,l,r)<<endl;
        }
    }
    return 0;
}

|