大概是随着树的结构的变化 答案也会变/kk

如果是犯了唐氏错误请踹我一脚/kel

// Problem: P2042 [NOI2005] 维护数列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2042
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <ctime>
#include <iostream>

using namespace std;

const int maxn = 4e6 + 10, inf = 1e9;

int n, m;

int tot, RT;
struct node {
    int ch[2];
    int val, data, siz, sum;
    int lmx, rmx, mmx;
    int revtag, addtag;
} t[maxn];
int st[maxn], top;
int newnode(int x)
{
    int tmp = st[top--];
    t[tmp].ch[0] = t[tmp].ch[1] = 0;
    t[tmp].sum = t[tmp].val = x;
    t[tmp].data = rand();
    t[tmp].siz = 1;
    t[tmp].revtag = 0;
    t[tmp].addtag = inf;
    return tmp;
}
void pushup(int x)
{
    t[x].siz = t[t[x].ch[0]].siz + t[t[x].ch[1]].siz + 1;
    t[x].sum = t[t[x].ch[0]].sum + t[t[x].ch[1]].sum + t[x].val;
    t[x].lmx = max(max(t[t[x].ch[0]].lmx, t[t[x].ch[0]].sum + t[x].val + t[t[x].ch[1]].lmx), 0);
    t[x].rmx = max(max(t[t[x].ch[1]].rmx, t[t[x].ch[1]].sum + t[x].val + t[t[x].ch[0]].rmx), 0);
    t[x].mmx = max(t[x].val, t[x].val + t[t[x].ch[0]].rmx + t[t[x].ch[1]].lmx);
    if (t[x].ch[0])
        t[x].mmx = max(t[x].mmx, t[t[x].ch[0]].mmx);
    if (t[x].ch[1])
        t[x].mmx = max(t[x].mmx, t[t[x].ch[1]].mmx);
}
void modify(int x, int v)
{
    t[x].sum = v * t[x].siz;
    t[x].val = v;
    t[x].addtag = v;
    t[x].lmx = t[x].rmx = max(0, t[x].sum);
    t[x].mmx = max(v, t[x].sum);
}
void rever(int x)
{
    t[x].revtag ^= 1;
    swap(t[x].lmx, t[x].rmx);
    swap(t[x].ch[0], t[x].ch[1]);
}
void pushdown(int x)
{
    if (t[x].revtag) {
        rever(t[x].ch[0]);
        rever(t[x].ch[1]);
        t[x].revtag = 0;
    }
    if (t[x].addtag != inf) {
        modify(t[x].ch[0], t[x].addtag);
        modify(t[x].ch[1], t[x].addtag);
        t[x].addtag = inf;
    }
}
void split(int rt, int rk, int& x, int& y)
{
    if (!rt) {
        x = y = 0;
        return;
    }
    pushdown(rt);
    if (t[t[rt].ch[0]].siz + 1 <= rk)
        x = rt, split(t[rt].ch[1], rk - t[t[rt].ch[0]].siz - 1, t[rt].ch[1], y);
    else
        y = rt, split(t[rt].ch[0], rk, x, t[rt].ch[0]);
    pushup(rt);
}
int merge(int x, int y)
{
    if (!x || !y)
        return x + y;
    pushdown(x), pushdown(y);
    if (t[x].data < t[y].data) {
        t[x].ch[1] = merge(t[x].ch[1], y), pushup(x);
        return x;
    } else {
        t[y].ch[0] = merge(x, t[y].ch[0]), pushup(y);
        return y;
    }
}
void del(int x)
{
    if (!x)
        return;
    st[++top] = x;
    if (t[x].ch[0])
        del(t[x].ch[0]);
    if (t[x].ch[1])
        del(t[x].ch[1]);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i < maxn; i++)
        st[++top] = i;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        RT = merge(RT, newnode(x));
    }
    while (m--) {
        string op;
        int x, y, z;
        cin >> op;
        if (op == "INSERT") {
            cin >> x >> y;
            int a = 0, b = 0;
            split(RT, x, a, b);
            for (int i = 1; i <= y; i++)
                cin >> z,
                    a = merge(a, newnode(z));
            RT = merge(a, b);
        } else if (op == "DELETE") {
            cin >> x >> y;
            int a = 0, b = 0, c = 0;
            y = x + y - 1;
            split(RT, y, a, b);
            split(a, x - 1, a, c);
            del(c);
            RT = merge(a, b);
        } else if (op == "MAKE-SAME") {
            cin >> x >> y >> z;
            int a = 0, b = 0, c = 0;
            y = x + y - 1;
            split(RT, y, a, b);
            split(a, x - 1, a, c);
            modify(c, z);
            a = merge(a, c);
            RT = merge(a, b);
        } else if (op == "REVERSE") {
            cin >> x >> y;
            int a = 0, b = 0, c = 0;
            y = x + y - 1;
            split(RT, y, a, b);
            split(a, x - 1, a, c);
            rever(c);
            a = merge(a, c);
            RT = merge(a, b);
        } else if (op == "GET-SUM") {
            cin >> x >> y;
            int a = 0, b = 0, c = 0;
            y = x + y - 1;
            split(RT, y, a, b);
            split(a, x - 1, a, c);
            cout << t[c].sum << "\n";
            a = merge(a, c);
            RT = merge(a, b);
        } else if (op == "MAX-SUM") {
            cout << t[RT].mmx << "\n";
        }
    }
    return 0;
}