提交记录

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define MINN -1e18

int n,q,a[1000010];

class SegmentTree {
    int tree[4000010], plus[4000010], cover[4000010];
public :
    void push_up(int p) {
        tree[p] = max(tree[p*2],tree[p*2+1]);
    }
    void push_down(int p) {
        if (cover[p] != MINN) {  // 先覆盖，再加
            plus[p*2] = plus[p*2+1] = plus[p];
            cover[p*2] = cover[p*2+1] = cover[p];
            tree[p*2] = tree[p*2+1] = cover[p];
        } else {
            plus[p*2] += plus[p], plus[p*2+1] += plus[p];
            tree[p*2] += plus[p], tree[p*2+1] += plus[p];
        }
        cover[p] = MINN, plus[p] = 0;
    }
    void build(int l=1,int r=n,int p=1) {
        tree[p] = MINN;
        cover[p] = MINN;
        if (l == r) {
            tree[p] = a[l];
            return;
        }
        int mid = l + (r - l) / 2;
        build(l,mid,p*2), build(mid+1,r,p*2+1);
        push_up(p);
    }
    void updateRangePlus(int l,int r,int d,int p=1,int cl=1,int cr=n) {
        if (r < cl or cr < l) {
            return;
        } else if (l <= cl and cr <= r) {
            tree[p] += d;
            if (cl < cr) {
                plus[p] += d;
            }
        } else {
            push_down(p);
            int mid = cl + (cr - cl) / 2;
            updateRangePlus(l,r,d,p*2,cl,mid);
            updateRangePlus(l,r,d,p*2+1,mid+1,cr);
            push_up(p);
        }
    }
    void updateRange(int l,int r,int d,int p=1,int cl=1,int cr=n) {
        if (r < cl or cr < l) {
            return;
        } else if (l <= cl and cr <= r) {
            tree[p] = cover[p] = d, plus[p] = 0;
        } else {
            push_down(p);
            int mid = cl + (cr - cl) / 2;
            updateRange(l,r,d,p*2,cl,mid);
            updateRange(l,r,d,p*2+1,mid+1,cr);
            push_up(p);
        }
    }
    int queryRangeMax(int l,int r,int p=1,int cl=1,int cr=n) {
        if (r < cl or cr < l) {
            return MINN;
        } else if (l <= cl and cr <= r) {
            return tree[p];
        } else {
            push_down(p);
            int mid = cl + (cr - cl) / 2;
            return max(queryRangeMax(l,r,p*2,cl,mid),queryRangeMax(l,r,p*2+1,mid+1,cr));
        }
    }
} Seg;

signed main() {
    scanf("%lld %lld",&n,&q);
    for (int i=1; i<=n; ++i) {
        scanf("%lld",&a[i]);
    }
    Seg.build();
    while (q--) {
        int opt,l,r,x;
        scanf("%lld %lld %lld",&opt,&l,&r);
        if (opt == 1) {
            scanf("%lld",&x);
            Seg.updateRange(l,r,x);
        } else if (opt == 2) {
            scanf("%lld",&x);
            Seg.updateRangePlus(l,r,x);
        } else {
            printf("%lld\n",Seg.queryRangeMax(l,r));
        }
    }
    return 0;
}