[NOI2005]维护数列

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\n", t[id].sum);
        }
        else printf("%d\n", t[root].maxlen);
    }
    return 0;
}