线段树60pts 求调

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 3;
const long long INF = -1e18;
int n, q;
inline int read();
int num[N];
struct Node
{
    int lc, rc;
    long long v, tag1, tag2;
} ns[N * 4];
int pos, root;
void update(int now)
{
    ns[now].v = max(ns[ns[now].lc].v, ns[ns[now].rc].v);
}
void init(int &now, int l, int r)
{
    now = ++pos;
    ns[now].tag1 = INF;
    if (l == r)
    {
        ns[now].v = num[l];
        return;
    }
    int mid = (l + r) / 2;
    init(ns[now].lc, l, mid);
    init(ns[now].rc, mid + 1, r);
    update(now);
}
void pushdown(int now, int l, int r)
{
    int lson = ns[now].lc, rson = ns[now].rc;
    if (ns[now].tag1 != INF)
    {
        ns[lson].v = ns[now].tag1;
        ns[rson].v = ns[now].tag1;
        ns[lson].tag1 = ns[now].tag1;
        ns[rson].tag1 = ns[now].tag1;
        ns[now].tag1 = INF;
    }
    if (ns[now].tag2 != 0)
    {
        ns[lson].v += ns[now].tag2;
        ns[rson].v += ns[now].tag2;
        ns[lson].tag2 += ns[now].tag2;
        ns[rson].tag2 += ns[now].tag2;
        ns[now].tag2 = 0;
    }
}
void edit1(int now, int l, int r, int x, int y, int k)
{
    pushdown(now, l, r);
    if (x <= l && r <= y)
    {
        ns[now].v = k;
        ns[now].tag1 = k;
        ns[now].tag2 = 0;
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid)
    {
        edit1(ns[now].lc, l, mid, x, y, k);
    }
    if (y >= mid + 1)
    {
        edit1(ns[now].rc, mid + 1, r, x, y, k);
    }
    update(now);
}
void edit2(int now, int l, int r, int x, int y, int k)
{
    pushdown(now, l, r);
    if (x <= l && r <= y)
    {
        ns[now].v += k;
        ns[now].tag2 += k;
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid)
    {
        edit2(ns[now].lc, l, mid, x, y, k);
    }
    if (y >= mid + 1)
    {
        edit2(ns[now].rc, mid + 1, r, x, y, k);
    }
    update(now);
}
long long query(int now, int l, int r, int x, int y)
{
    pushdown(now, l, r);
    if (x <= l && r <= y)
    {
        return ns[now].v;
    }
    int mid = (l + r) / 2;
    long long ans = INF;
    if (x <= mid)
    {
        ans = max(ans, query(ns[now].lc, l, mid, x, y));
    }
    if (y >= mid + 1)
    {
        ans = max(ans, query(ns[now].rc, mid + 1, r, x, y));
    }
    return ans;
}
signed main()
{
    freopen("P1253_7.in", "r", stdin);
    freopen("P1253_7.out", "w", stdout);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        num[i] = read();
    }
    init(root, 1, n);
    while (q--)
    {
        int opt;
        cin >> opt;
        if (opt == 1)
        {
            int x = read(), y = read(), k = read();
            edit1(root, 1, n, x, y, k);
        }
        else if (opt == 2)
        {
            int x = read(), y = read(), k = read();
            edit2(root, 1, n, x, y, k);
        }
        else
        {
            int x = read(), y = read();
            cout << query(root, 1, n, x, y) << '\n';
        }
    }
    return 0;
}
inline int read()
{
    char ch = getchar();
    int f = 1, tot = 0;
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        tot = tot * 10 + ch - '0';
        ch = getchar();
    }
    return f * tot;
}