题目地址：洛谷：【P2042】[NOI2005]维护数列 – 洛谷、BZOJ：Problem 1500. — [NOI2005]维修数列

题目描述

请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）

输入输出格式

输入格式：
输入文件的第 1 行包含两个数 N 和 M，N 表示初始时数列中数的个数，M 表示要进行的操作数目。 第 2 行包含 N 个数字，描述初始时的数列。 以下 M 行，每行一条命令，格式参见问题描述中的表格

输出格式：
对于输入数据中的 GET-SUM 和 MAX-SUM 操作，向输出文件依次打印结 果，每个答案（数字）占一行。

输入输出样例

输入样例#1：

9 8
2 -6 3 5 1 -5 -3 6 3 
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM

输出样例#1：

-1
10
1
10

说明

你可以认为在任何时刻，数列中至少有 1 个数。
输入数据一定是正确的，即指定位置的数在数列中一定存在。
50%的数据中，任何时刻数列中最多含有 30 000 个数；
100%的数据中，任何时刻数列中最多含有 500 000 个数。
100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。
100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 。

样例说明：

题解

这个题是Splay模板之集大全者哇，A掉了Splay的常见用法基本就见过了。
我们分开说这些操作吧。

插入删除修改翻转

这些操作都可以用split-perform这种模式去写。
以插入为例，首先对插入的内容现场建成splay，然后把x-1位置splay到根，x+tot位置splay到根的右儿子。在x+tot位置的左儿子处把新的splay挂上去就行。split操作就是上面的两次splay。
具体的实现可以参考代码。

求和求最大子列

可以维护四个量，区间和、区间最大子列，区间以左侧为起点的最大子列，区间以右侧为起点的最大子列。操作后动态更新这些量，询问的时候先split再查即可。
更新的方法如下。
区间最大子列：max(左儿子右侧最大子列+中间值+右儿子左侧最大子列，左右儿子的最大子列)
区间左侧最大子列：max(左儿子和+中间值+右儿子左侧最大子列，左儿子左侧最大子列)
右侧类似。

其他细节看代码吧。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc(); 
    while (c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while (c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline int readstr(char str[], int startpos) {
    char c = '*';
    int siz = startpos;
    while((c < 'A' || c > 'Z') && c != '-') c = fgc();
    while((c >= 'A' && c <= 'Z') || c == '-') {
        str[siz++] = c;
        c = fgc();
    }
    str[siz] = '\0';
    return siz - startpos;
}

inline int readop() {
    char ops[20];
    readstr(ops, 0);
    if(ops[2] == 'S') return 1;
    if(ops[2] == 'L') return 2;
    if(ops[2] == 'K') return 3;
    if(ops[2] == 'V') return 4;
    if(ops[2] == 'T') return 5;
    if(ops[2] == 'X') return 6;
    return 0;
}

// variables

const int MAXN = 500005, MAXI = 4000005, INF = 1e9;

int n, m, op, xt, lent;
LL ct, a[MAXI];

// splay

struct Node {
    LL val, mxs, mxl, mxr, sum;
    bool rev, rep;
    int ch[2], siz, fa;
} tr[MAXN]; 
int tot = 0, sta[MAXN], stop = 0, rt = 0;

inline void update(int p) {
    int lch = tr[p].ch[0], rch = tr[p].ch[1];
    tr[p].siz = tr[lch].siz + tr[rch].siz + 1;
    tr[p].sum = tr[lch].sum + tr[rch].sum + tr[p].val;
    tr[p].mxs = std::max(tr[lch].mxr + tr[p].val + tr[rch].mxl, std::max(tr[lch].mxs, tr[rch].mxs));
    tr[p].mxl = std::max(tr[lch].mxl, tr[lch].sum + tr[p].val + tr[rch].mxl);
    tr[p].mxr = std::max(tr[rch].mxr, tr[rch].sum + tr[p].val + tr[lch].mxr);
}

inline void pushdown(int p) {
    int lch = tr[p].ch[0], rch = tr[p].ch[1];
    if(tr[p].rep) {
        if(lch) {
            tr[lch].rep = true;
            tr[lch].val = tr[p].val;
            tr[lch].sum = tr[p].val * tr[lch].siz;
            if(tr[p].val >= 0) {
                tr[lch].mxl = tr[lch].mxr = tr[lch].mxs = tr[lch].sum;
            } else {
                tr[lch].mxl = tr[lch].mxr = 0;
                tr[lch].mxs = tr[p].val;
            }
        }
        if(rch) {
            tr[rch].rep = true;
            tr[rch].val = tr[p].val;
            tr[rch].sum = tr[p].val * tr[rch].siz;
            if(tr[p].val >= 0) {
                tr[rch].mxl = tr[rch].mxr = tr[rch].mxs = tr[rch].sum;
            } else {
                tr[rch].mxl = tr[rch].mxr = 0;
                tr[rch].mxs = tr[p].val;
            }
        }
        tr[p].rep = tr[p].rev = false;
    }
    if(tr[p].rev) {
        std::swap(tr[lch].mxl, tr[lch].mxr);
        std::swap(tr[lch].ch[0], tr[lch].ch[1]);
        std::swap(tr[rch].mxl, tr[rch].mxr);
        std::swap(tr[rch].ch[0], tr[rch].ch[1]);
        tr[lch].rev = !tr[lch].rev;
        tr[rch].rev = !tr[rch].rev;
        tr[p].rev = false;
    }
}

inline int newnode() {
    int p;
    if(stop > 0) {
        p = sta[--stop];
    } else {
        p = ++tot;
    } 
    memset(tr + p, 0, sizeof(Node));
    return p;
}

inline void delnode(int a) {
    sta[stop++] = a;
}

inline bool isleft(int p) {
    return tr[tr[p].fa].ch[0] == p;
}

inline void rotate(int p) { // p is child
    bool type = !isleft(p);
    int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[fa].ch[type] = tr[p].ch[!type];
    tr[p].ch[!type] = fa;
    tr[tr[fa].ch[type]].fa = fa;
    if(ffa) tr[ffa].ch[!isleft(fa)] = p;
    tr[p].fa = tr[fa].fa;
    tr[fa].fa = p;
    update(fa);
    update(p);
}

inline void splay(int p, int tar) {
    for(int fa; (fa = tr[p].fa) != tar; rotate(p)) {
        if(tr[tr[p].fa].fa != tar) {
            rotate(isleft(fa) == isleft(p) ? fa : p);
        }
    }
    if(!tar) rt = p;
}

inline int find(int p, int rk) {
    pushdown(p);
    int lch = tr[p].ch[0], rch = tr[p].ch[1];
    if(tr[lch].siz + 1 == rk) return p;
    else if(tr[lch].siz >= rk) return find(lch, rk);
    else return find(rch, rk - tr[lch].siz - 1);
}

inline int build(int fa, int l, int r) {
    if(l > r) return 0;
    int p = newnode();
    if(l == r) {
        tr[p].siz = 1;
        tr[p].val = tr[p].sum = tr[p].mxs = a[l];
        tr[p].mxl = tr[p].mxr = a[l] >= 0 ? a[l] : 0;
        tr[p].fa = fa;
        return p;
    }
    int mid = (l + r) >> 1;
    tr[p].ch[0] = build(p, l, mid - 1);
    tr[p].ch[1] = build(p, mid + 1, r);
    tr[p].fa = fa;
    tr[p].val = a[mid];
    update(p);
    return p;
}

inline void insert(int x, int len) {
    for(int i = 1; i <= len; i++) {
        a[i] = readint();
    }
    int p = build(0, 1, len), a = find(rt, x + 1), b = find(rt, x + 2);
    splay(a, 0);
    splay(b, a);
    tr[p].fa = b;
    tr[b].ch[0] = p;
    update(b);
    update(a);
} 

inline void eraset(int p) {
    if(!p) return;
    delnode(p);
    eraset(tr[p].ch[0]);
    eraset(tr[p].ch[1]);
}

inline void erase(int x, int len) {
    int a = find(rt, x), b = find(rt, x + len + 1);
    splay(a, 0);
    splay(b, a);
    eraset(tr[b].ch[0]);
    tr[b].ch[0] = 0;
    update(b);
    update(a);
}

inline void replace(int x, int len, LL val) {
    int a = find(rt, x), b = find(rt, x + len + 1);
    splay(a, 0);
    splay(b, a);
    int p = tr[b].ch[0];
    tr[p].val = val;
    tr[p].rep = true;
    tr[p].sum = val * tr[p].siz;
    if(val >= 0) {
        tr[p].mxl = tr[p].mxr = tr[p].mxs = tr[p].sum;
    } else {
        tr[p].mxl = tr[p].mxr = 0;
        tr[p].mxs = val;
    }
    update(b);
    update(a);
}

inline void reverse(int x, int len) {
    int a = find(rt, x), b = find(rt, x + len + 1);
    splay(a, 0);
    splay(b, a);
    int p = tr[b].ch[0];
    if(!tr[p].rep) {
        tr[p].rev = !tr[p].rev;
        std::swap(tr[p].mxl, tr[p].mxr);
        std::swap(tr[p].ch[0], tr[p].ch[1]);
        update(b);
        update(a);
    }
}

inline LL querysum(int x, int len) {
    int a = find(rt, x), b = find(rt, x + len + 1);
    splay(a, 0);
    splay(b, a);
    int p = tr[b].ch[0];
    return tr[p].sum;
}

inline LL querymxs() {
    int a = find(rt, 1), b = find(rt, n);
    splay(a, 0);
    splay(b, a);
    int p = tr[b].ch[0];
    return tr[p].mxs;
}

int main() {
    n = readint();
    m = readint();
    tr[0].mxs = a[1] = a[n + 2] = -INF;
    for(int i = 1; i <= n; i++) {
        a[i + 1] = readint();
    }
    rt = build(0, 1, n + 2);
    n += 2;
    while(m--) {
        op = readop();
        if(op != 6) {
            xt = readint();
            lent = readint();
        }
        if(op == 1) {
            insert(xt, lent);
            n += lent;
        }
        if(op == 2) {
            erase(xt, lent);
            n -= lent;
        }
        if(op == 3) {
            ct = readint();
            replace(xt, lent, ct);
        }
        if(op == 4) {
            reverse(xt, lent);
        }
        if(op == 5) {
            printf("%lld\n", querysum(xt, lent));
        }
        if(op == 6) {
            printf("%lld\n", querymxs());
        }
    }
    return 0;
}