首先，这题我是没A的。。太毒瘤了
题目本身不难，都是\(Splay\)的基操，但是细节真的容易挂。
调了好久自闭了，果断放弃。。
希望本节目停更。
放上最终版本
#include <cstdio>
#include <algorithm>
#define INF 2147483647
#define lc t[u].ch[0]
#define rc t[u].ch[1]
using namespace std;
inline int read(){
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1;else w = 1; ch = getchar();}
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
return s * w;
}
const int MAXINSERTLEN = 4000010;
struct SplayTree{
int ch[2], fa, size, val, sum, lm, rm, m, lazy, lz, to;
}t[MAXINSERTLEN];
int str[MAXINSERTLEN];
int num, root, n, len, a, b, c, tot;
void pushup(int u){
t[u].size = t[lc].size + t[rc].size + 1;
t[u].sum = t[lc].sum + t[rc].sum + t[u].val;
t[u].lm = max(t[lc].lm, t[lc].sum + t[u].val + t[rc].lm);
t[u].rm = max(t[rc].rm, t[rc].sum + t[u].val + t[lc].rm);
t[u].m = max(max(t[lc].m, t[rc].m), t[lc].rm + t[u].val + t[rc].lm);
}
void pushdown(int u){
if(t[u].lz){
t[lc].lz = t[rc].lz = 1;
t[lc].to = t[rc].to = t[lc].val = t[rc].val = t[u].to;
t[u].lz = t[u].lazy = 0;
t[lc].sum = t[lc].lm = t[lc].rm = t[lc].m = t[lc].size * t[u].to;
t[rc].sum = t[rc].lm = t[rc].rm = t[rc].m = t[rc].size * t[u].to;
}
if(t[u].lazy){
t[lc].lazy ^= 1; t[rc].lazy ^= 1;
t[u].lazy = 0;
swap(lc, rc);
swap(t[u].lm, t[u].rm);
}
}
void rotate(int x){
int y = t[x].fa; int z = t[y].fa;
pushdown(y); pushdown(x); int k = t[y].ch[1] == x;
t[z].ch[t[z].ch[1] == y] = x; t[x].fa = z;
t[y].ch[k] = t[x].ch[k ^ 1]; t[t[x].ch[k ^ 1]].fa = y;
t[x].ch[k ^ 1] = y; t[y].fa = x;
pushup(y); pushup(x);
}
void Splay(int x, int goal){
while(t[x].fa != goal){
int y = t[x].fa; int z = t[y].fa;
pushdown(y); pushdown(x);
if(z != goal)
(t[z].ch[0] == y) ^ (t[y].ch[0] == x) ? rotate(x) : rotate(y);
rotate(x);
}
if(goal == 0) root = x;
}
int build(int l, int r){
int id = ++num;
int mid = (l + r) >> 1;
t[id].val = str[mid];
if(mid > l){
t[id].ch[0] = build(l, mid - 1);
t[t[id].ch[0]].fa = id;
}
if(mid < r){
t[id].ch[1] = build(mid + 1, r);
t[t[id].ch[1]].fa = id;
}
pushup(id);
return id;
}
inline int findKth(int k){
int u = root;
while(1){
pushdown(u);
if(t[t[u].ch[0]].size >= k) u = t[u].ch[0];
else if(t[t[u].ch[0]].size == k - 1) return u;
else k -= t[t[u].ch[0]].size + 1, u = t[u].ch[1];
}
}
char opt;
int main(){
tot = (2 + (len = read())); n = read(); t[0].m = -INF;
root = ++num; t[num].val = -INF;
t[++num].fa = root; t[num].val = -INF;
t[root].ch[1] = num; t[num].size = 1; t[root].size = 2;
for(int i = 1; i <= len; ++i) str[i] = read();
a = build(1, len); t[t[root].ch[1]].ch[0] = a;
t[a].fa = t[root].ch[1];
pushup(t[root].ch[1]); pushup(root);
for(int i = 1; i <= n; ++i){
opt = getchar();
while(opt < 'A' || opt > 'Z') opt = getchar();
if(opt == 'G'){
a = read(); b = read();
int l = findKth(a), r = findKth(a + b + 1);
Splay(l, 0); Splay(r, l);
printf("%d\n", t[t[t[root].ch[1]].ch[0]].sum);
}
if(opt == 'R'){
a = read(); b = read();
int l = findKth(a), r = findKth(a + b + 1);
Splay(l, 0); Splay(r, l);
a = t[t[root].ch[1]].ch[0];
t[a].lazy ^= 1;
}
if(opt == 'M'){
getchar();
if(getchar() == 'X'){
while(getchar() != 'M');
a = findKth(tot);
Splay(findKth(1), 0); Splay(a, root);
printf("%d\n", t[t[a].ch[0]].m);
}
else{
a = read(); b = read(); c = read();
int l = findKth(a), r = findKth(a + b + 1);
Splay(l, 0); Splay(r, l);
a = t[t[root].ch[1]].ch[0];
t[a].lz = 1; t[a].to = t[a].val = c; t[a].sum = c * t[a].size; t[a].lm = t[a].rm = max(c * t[a].size, 0);
pushdown(a); Splay(a, 0);
}
}
if(opt == 'I'){
a = read(); tot += (len = read());
for(int j = 1; j <= len; ++j) str[i] = read();
int l = findKth(a), r = findKth(a + 1);
Splay(l, 0); Splay(r, l);
a = t[root].ch[1]; b = build(1, len);
t[a].ch[0] = b; t[b].fa = a; pushup(a); Splay(a, 0);
}
if(opt == 'D'){
a = read(); tot -= (b = read());
int l = findKth(a), r = findKth(a + b + 1);
Splay(l, 0); Splay(r, l);
t[t[root].ch[1]].ch[0] = 0;
pushup(t[root].ch[1]);
Splay(t[root].ch[1], 0);
}
}
return 0;
}
【洛谷 P2042】 [NOI2005]维护数列（自闭记第一期）
原文：https://www.cnblogs.com/Qihoo360/p/10197634.html