蒟蒻求助线段树

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define ll long long
#define int ll
using namespace std;

const int INF = 1e18 + 7;

int rd() {
    int x = 0, w = 1;
    char c = getchar();

    while(c < '0' || c > '9') {
        if(c == '-') w = -1;
        c = getchar();
    }

    while(c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }

    return x * w;
}

const int N = 1e7 + 5;

int n, a[N];
int q;

struct Tree {
    int l, r;
    int dat;
    int tag1, tag2;

    #define tag1(x) tr[x].tag1
    #define l(x) tr[x].l
    #define r(x) tr[x].r
    #define ls (p << 1)
    #define rs (ls | 1)
    #define dat(x) tr[x].dat
    #define tag2(x) tr[x].tag2

}tr[N << 2];

void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    tag1(p) = INF;
    if(l == r) {
        dat(p) = a[l];
        return ;
    }

    int mid = (r - l) / 2 + l;
    build(ls, l, mid);
    build(rs, mid + 1, r);

    dat(p) = max(dat(ls), dat(rs));
}

void spr(int p) {
    if(tag1(p) != INF) {
        tag1(ls) = tag1(rs) = tag1(p);
        tag2(p) = tag2(ls) = tag2(rs) = 0;
        dat(ls) = dat(rs) = tag1(p);
        tag1(p) = INF;
    }

    if(tag2(p) != 0) {
        dat(ls) += tag2(p);
        dat(rs) += tag2(p);
        tag2(ls) += tag2(p);
        tag2(rs) += tag2(p);
        tag2(p) = 0;
    }
}

void change(int p, int l, int r, int del, int opt) {
    if(l <= l(p) && r(p) <= r) {
        if(opt == 1) {
            tag1(p) = del;
            dat(p) = del;
            tag2(p) = 0;
        } else {
            spr(p);
            dat(p) += del;
            tag2(p) += del;
        }

        return ;
    }

    spr(p);

    int mid = (r(p) - l(p)) / 2 + l(p);

    if(l <= mid) change(ls, l, r, del, opt);
    if(r > mid) change(rs, l, r, del, opt);

    dat(p) = max(dat(ls), dat(rs));
}

int ask(int p, int l, int r) {
    if(l <= l(p) && r(p) <= r) return dat(p);

    spr(p);

    int mid = (r(p) - l(p)) / 2 + l(p);
    int res = -INF;

    if(l <= mid) res = max(res, ask(ls, l, r));
    if(r > mid) res = max(res, ask(rs, l, r));

    dat(p) = max(dat(ls), dat(rs));

    return res;
}

signed main() {
    n = rd(), q = rd();
    for(int i = 1; i <= n; ++i) a[i] = rd();

    build(1, 1, n);
    while(q--) {
        int opt = rd(), l = rd(), r = rd();
        if(opt <= 2) {
            int del = rd();
            change(1, l, r, del, opt);
        } else printf("%lld\n", ask(1, l, r));
    }
    return 0;
}