P1253

评测记录

#include<bits/stdc++.h>
#define int long long
#define ls (p*2)
#define rs (p*2+1)
using namespace std;
struct node{
    int lft,rgt,maxn,add,chg;
    bool b;
}a[40000200];
int n,q;
void up(int p){
    a[p].maxn=max(a[ls].maxn,a[rs].maxn);
    return;
}
void make_chg(int p,int x){
    a[p].b=1;
    a[p].add=0;
    a[p].chg=x;
    a[p].maxn=x;
    return ;
}
void make_add(int p,int x){
    if(a[p].b){
        make_chg(p,a[p].add+a[p].chg);
    }else{
        a[p].add+=x;
        a[p].maxn+=x;
    }
    return ;
}
void build(int p,int l,int r){
    a[p].lft=l;
    a[p].rgt=r;
    if(l==r){
        cin >> a[p].maxn;
        return;
    }
    int mid=(l+r)/2;
    build(ls,l,mid);
    build(rs,mid+1,r);
    up(p);
}
void down(int p){
    if(a[p].b){
        make_chg(ls,a[p].chg);
        make_chg(rs,a[p].chg);
    }else{
        make_add(ls,a[p].add);
        make_add(rs,a[p].add);
    }
    a[p].b=0;
    a[p].add=0;
    return ;
}
void chg(int p,int l,int r,int x){
    if(a[p].lft>=l&&a[p].rgt<=r){
        make_chg(p,x);
        return ;
    }
    down(p);
    if(a[ls].rgt>=l){
        chg(ls,l,r,x);
    }
    if(a[rs].lft<=r){
        chg(rs,l,r,x);
    }
    up(p);
    return;
}
void add(int p,int l,int r,int x){
    if(a[p].lft>=l&&a[p].rgt<=r){
        make_add(p,x);
        return ;
    }
    down(p);
    if(a[ls].rgt>=l){
        add(ls,l,r,x);
    }
    if(a[rs].lft<=r){
        add(rs,l,r,x);
    }
    up(p);
    return;
}
int query(int p,int l,int r){
    if(a[p].lft>=l&&a[p].rgt<=r){
        return a[p].maxn;
    }
    down(p);
    int ret=LONG_LONG_MIN;
    if(a[ls].rgt>=l){
        ret=max(ret,query(ls,l,r));
    }
    if(a[rs].lft<=r){
        ret=max(ret,query(rs,l,r));
    }
    return ret;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    build(1,1,n);
    while(q--){
        int op,l,r,x;
        cin >> op >> l >> r;
        if(op==1){
            cin >> x;
            chg(1,l,r,x);
        }
        if(op==2){
            cin >> x;
            add(1,l,r,x);
        }
        if(op==3){
            cout << query(1,l,r) << '\n';
        }
    }
    return 0;
}