题面大意：
使用平衡树维护一个数列，支持插入，修改，删除，翻转，求和，求最大和这 (6) 个操作.
题意分析：
Splay 裸题，几乎各种操作都有了，这个代码就发给大家当个模板吧.
最后求最大和的时候可以事先维护好最大和，然后输出即可。
代码：
#include <cstdio>
#include <climits>
#include <algorithm>
#include <iostream>
#define maxn 1000001
using namespace std;
inline int read() {
int x = 0;
bool f = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = 1; c = getchar();}
while ('0' <= c && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
if (f) {
x = -x;
}
return x;
}
int stack[maxn], top, v[maxn];
struct Splay {
#define T(x) (tree[f[x]][1]==x)
#define ls(x) tree[x][0]
#define rs(x) tree[x][1]
int tree[maxn][2], f[maxn], size[maxn], val[maxn];
int sum[maxn], L[maxn], R[maxn], Max[maxn];
bool rev[maxn], mark[maxn];
int root, len;
void cov_tag(int x, int v) {
if (!x) return;
sum[x] = size[x] * v;
val[x] = v;
L[x] = R[x] = Max[x] = max(v, sum[x]);
mark[x] = 1, rev[x] = 0;
}
void rev_tag(int x) {
if (!x) return;
swap(L[x], R[x]);
swap(ls(x), rs(x));
rev[x] ^= 1;
}
void pushdown(int x) {
if (rev[x]) {
rev_tag(ls(x));
rev_tag(rs(x));
rev[x] = 0;
}
if (mark[x]) {
cov_tag(ls(x), val[x]),
cov_tag(rs(x), val[x]);
mark[x] = 0;
}
}
void updata(int x) {
size[x] = size[ls(x)] + size[rs(x)] + 1;
Max[x] = max(max(Max[ls(x)], Max[rs(x)]), max(0, R[ls(x)]) + val[x] + max(0, L[rs(x)]));
L[x] = max(L[ls(x)], sum[ls(x)] + val[x] + max(0, L[rs(x)]));
R[x] = max(R[rs(x)], sum[rs(x)] + val[x] + max(0, R[ls(x)]));
sum[x] = sum[ls(x)] + sum[rs(x)] + val[x];
}
int get() {
int x;
x = top ? stack[top--] : ++len;
ls(x) = rs(x) = f[x] = 0;
rev[x] = mark[x] = 0;
size[x] = 1;
sum[x] = L[x] = R[x] = val[x] = -1e9;
return x;
}
void build(int fa, int l, int r, int& x) {
if (l > r) return;
int mid = (l + r) >> 1;
x = get(), f[x] = fa, val[x] = v[mid];
if (l == r) {
size[x] = 1;
Max[x] = L[x] = R[x] = sum[x] = val[x];
return;
}
build(x, l, mid - 1, ls(x));
build(x, mid + 1, r, rs(x));
updata(x);
}
void init(int n) {
L[0] = R[0] = Max[0] = -1e9;
len = 2, root = 1;
rs(1) = size[1] = 2, L[1] = R[1] = val[1] = sum[1] = -1e9;
f[2] = size[2] = 1, L[2] = R[2] = val[2] = sum[2] = -1e9;
for (int i = 1; i <= n; i++) v[i] = read();
build(2, 1, n, ls(2));
updata(2), updata(1);
}
void move(int x) {
int fa = f[x], son = tree[x][T(x) ^ 1];
tree[x][T(x) ^ 1] = fa;
tree[fa][T(x)] = son;
if (son) f[son] = fa;
f[x] = f[fa];
if (f[x]) tree[f[x]][T(fa)] = x;
f[fa] = x;
updata(fa);
updata(x);
}
void splay(int x) {
while (f[x]) {
if (f[f[x]]) T(x) == T(f[x]) ? move(f[x]) : move(x);
move(x);
}
root = x;
}
int find(int x, int i) {
pushdown(i);
if (size[ls(i)] + 1 == x) return i;
if (x <= size[ls(i)]) return find(x, ls(i));
return find(x - size[ls(i)] - 1, rs(i));
}
void insert() {
int x = read() + 1, y = x + 1, tot = read();
x = find(x, root), splay(x);
y = find(y, root), splay(y);
if (f[x] != root) move(x);
for (int i = 1; i <= tot; i++) v[i] = read();
build(x, 1, tot, rs(x));
updata(x);
updata(y);
}
void reuse(int x) {
if (!x) return;
stack[++top] = x;
reuse(ls(x));
reuse(rs(x));
}
void Del() {
int x = read(), y = read() + x - 1;
x = find(x, root), splay(x);
y = find(y + 2, root), splay(y);
if (f[x] != root) move(x);
reuse(rs(x));
f[rs(x)] = 0, rs(x) = 0;
updata(x);
updata(y);
}
void cover() {
int x = read(), y = read() + x - 1, v = read();
x = find(x, root), splay(x);
y = find(y + 2, root), splay(y);
if (f[x] != root) move(x);
cov_tag(rs(x), v);
updata(x);
updata(y);
}
void reverse() {
int x = read(), y = read() + x - 1;
x = find(x, root), splay(x);
y = find(y + 2, root), splay(y);
if (f[x] != root) move(x);
rev_tag(rs(x));
updata(x);
updata(y);
}
void query_sum() {
int x = read(), y = read() + x - 1;
x = find(x, root), splay(x);
y = find(y + 2, root), splay(y);
if (f[x] != root) move(x);
printf("%d
", sum[rs(x)]);
}
void query_max() {
printf("%d
", Max[root]);
}
} splay;
int main()
{
freopen("sequence.in", "r", stdin);
freopen("sequence.out", "w", stdout);
int n, m;
scanf("%d %d", &n, &m);
splay.init(n); // 先插入 n 个数并建立平衡树
while (m--)
{
string ss;
cin >> ss;
if (ss[0] == 'I') { // 插入操作
splay.insert();
}
if (ss[0] == 'D') { // 删除操作
splay.Del();
}
if (ss[0] == 'M' && ss[2] == 'K') { // 修改操作
splay.cover();
}
if (ss[0] == 'R') { // 旋转操作
splay.reverse();
}
if (ss[0] == 'G') { // 求和操作
splay.query_sum();
}
if (ss[0] == 'M' && ss[2] == 'X') { // 修改操作
splay.query_max();
}
}
return 0;
}