Splay模板题（很难调）
# include <bits/stdc++.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(5e5 + 10), INF(2147483647);
IL ll Read(){
RG char c = getchar(); RG ll x = 0, z = 1;
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
return x * z;
}
int n, m, cnt, root, a[_];
struct Tree{
int fa, ch[2], tag, rev, maxl, maxr, maxlen, sum, val, sz;
IL void Init(){ fa = ch[0] = ch[1] = tag = rev = maxl = maxr = sum = val = sz = 0; maxlen = -INF; }
} t[_];
int tra[_], tot;
# define ls t[x].ch[0]
# define rs t[x].ch[1]
IL void Update(RG int x){
if(!x) return; if(!ls) t[ls].Init(); if(!rs) t[rs].Init();
t[x].sz = t[ls].sz + t[rs].sz + 1;
t[x].sum = t[ls].sum + t[rs].sum + t[x].val;
t[x].maxl = max(t[ls].maxl, t[x].val + t[ls].sum + t[rs].maxl);
t[x].maxr = max(t[rs].maxr, t[x].val + t[rs].sum + t[ls].maxr);
t[x].maxlen = max(t[ls].maxlen, max(t[rs].maxlen, t[ls].maxr + t[rs].maxl + t[x].val));
}
IL void Pushdown(RG int x){
if(!ls) t[ls].Init(); if(!rs) t[rs].Init();
if(t[x].tag){
if(ls) t[ls].tag = 1, t[ls].val = t[x].val, t[ls].sum = t[x].val * t[ls].sz;
if(rs) t[rs].tag = 1, t[rs].val = t[x].val, t[rs].sum = t[x].val * t[rs].sz;
if(t[x].val >= 0){
if(ls) t[ls].maxl = t[ls].maxr = t[ls].maxlen = t[ls].sum;
if(rs) t[rs].maxl = t[rs].maxr = t[rs].maxlen = t[rs].sum;
}
else{
if(ls) t[ls].maxl = t[ls].maxr = 0, t[ls].maxlen = t[ls].val;
if(rs) t[rs].maxl = t[rs].maxr = 0, t[rs].maxlen = t[rs].val;
}
t[x].tag = t[x].rev = 0;
}
if(t[x].rev){
t[ls].rev ^= 1; t[rs].rev ^= 1; t[x].rev = 0;
swap(t[ls].maxl, t[ls].maxr); swap(t[rs].maxl, t[rs].maxr);
swap(t[ls].ch[0], t[ls].ch[1]); swap(t[rs].ch[0], t[rs].ch[1]);
}
}
IL bool Son(RG int x){ return t[t[x].fa].ch[1] == x; }
IL void Rot(RG int x){
RG int y = t[x].fa, z = t[y].fa, c = Son(x);
t[z].ch[Son(y)] = x; t[x].fa = z;
t[y].ch[c] = t[x].ch[!c]; t[t[y].ch[c]].fa = y;
t[x].ch[!c] = y; t[y].fa = x;
Update(y);
}
IL void Splay(RG int x, RG int rt){
for(RG int y = t[x].fa; y != rt; Rot(x), y = t[x].fa)
if(t[y].fa != rt) Son(x) ^ Son(y) ? Rot(x) : Rot(y);
Update(x);
if(!rt) root = x;
}
IL void Build(RG int &x, RG int l, RG int r, RG int fa){
if(l > r) return;
if(!x){ if(tot) x = tra[tot--]; else x = ++cnt; t[x].Init(); }
RG int mid = (l + r) >> 1;
Build(ls, l, mid - 1, x);
Build(rs, mid + 1, r, x);
t[x].maxlen = t[x].val = a[mid]; t[x].fa = fa; t[x].sz = 1;
t[x].maxl = t[x].maxr = max(0, t[x].val);
Update(x);
}
IL int Find(RG int x, RG int k){
Pushdown(x);
if(k == t[ls].sz + 1) return x;
else if(k <= t[ls].sz) return Find(ls, k);
else return Find(rs, k - t[ls].sz - 1);
}
IL void Recycle(RG int x){ if(!x) return; tra[++tot] = x; Recycle(ls); Recycle(rs); }
IL int Split(RG int x, RG int y){
RG int l = Find(root, x), r = Find(root, y);
Splay(l, 0); Splay(r, root);
return t[r].ch[0];
}
# undef ls
# undef rs
int main(RG int argc, RG char* argv[]){
RG char op[20]; RG int pos, x, rt, c;
n = Read(); m = Read();
a[1] = a[n + 2] = -2333;
for(RG int i = 1; i <= n; i++) a[i + 1] = Read();
Build(root, 1, n + 2, 0);
while(m--){
scanf(" %s", op);
if(op[0] == 'I'){
pos = Read() + 1; x = Read(); rt = 0;
for(RG int i = 1; i <= x; i++) a[i] = Read();
Build(rt, 1, x, 0); Split(pos, pos + 1);
t[t[root].ch[1]].ch[0] = rt; t[rt].fa = t[root].ch[1];
Update(t[rt].fa); Update(root);
}
else if(op[0] == 'D'){
pos = Read() + 1; x = Read();
RG int id = Split(pos - 1, pos + x);
Recycle(id); t[t[root].ch[1]].ch[0] = 0;
Update(t[root].ch[1]); Update(root);
}
else if(op[0] == 'M' && op[2] == 'K'){
pos = Read() + 1; x = Read(); c = Read();
RG int id = Split(pos - 1, pos + x);
t[id].val = c; t[id].sum = t[id].sz * c;
if(c >= 0) t[id].maxl = t[id].maxr = t[id].maxlen = t[id].sum;
else t[id].maxl = t[id].maxr = 0, t[id].maxlen = t[id].val;
Update(t[id].fa); Update(root);
t[id].tag = 1;
}
else if(op[0] == 'R'){
pos = Read() + 1; x = Read();
RG int id = Split(pos - 1, pos + x);
if(!t[id].tag){
swap(t[id].ch[0], t[id].ch[1]);
swap(t[id].maxl, t[id].maxr);
t[id].rev ^= 1;
Update(t[id].fa); Update(root);
}
}
else if(op[0] == 'G'){
pos = Read() + 1; x = Read();
RG int id = Split(pos - 1, pos + x);
printf("%d
", t[id].sum);
}
else printf("%d
", t[root].maxlen);
}
return 0;
}