题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1500

解法：Crash大神的论文上有详细解题方法，实现加调试花了很久很久。然后总算A掉啦。这个题都没过，说

啥学过Splay啊。

///BZOJ 1500

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int maxn = 510010;
#define key_val ch[ch[root][1]][0]

int fa[maxn], ch[maxn][2], w[maxn], siz[maxn], sum[maxn], lmax[maxn], rmax[maxn], ans[maxn];
bool rev[maxn];
bool same[maxn];
int a[maxn];
char s[20];
int st[maxn];
int n, m, T, tot, root, top;

int newnode(){
    int num;
    if(top) num=st[top--];
    else num=++tot;
    ch[num][0]=ch[num][1]=fa[num]=0;
    same[num]=rev[num]=0;
    siz[num]=1;
    sum[num]=w[num]=rmax[num]=lmax[num]=-inf;
    return num;
}

void pushup(int x)
{
    if(!x) return;
    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+w[x];
    lmax[x]=max(lmax[ch[x][0]], sum[ch[x][0]]+w[x]+max(0,lmax[ch[x][1]]));
    rmax[x]=max(rmax[ch[x][1]], sum[ch[x][1]]+w[x]+max(0,rmax[ch[x][0]]));
    ans[x]=max(max(ans[ch[x][0]],ans[ch[x][1]]), max(0,rmax[ch[x][0]])+w[x]+max(0,lmax[ch[x][1]]));
}

void reverse(int x){
    if(!x) return;
    swap(lmax[x], rmax[x]);
    swap(ch[x][0], ch[x][1]);
    rev[x]^=1;
}

void replace(int x, int d){
    if(!x) return;
    w[x]=d;
    sum[x]=d*siz[x];
    lmax[x]=rmax[x]=ans[x]=max(d,d*siz[x]);
    same[x]=1;
    rev[x]=0;
}

void pushdown(int x){
    if(rev[x]){
        if(ch[x][0]) reverse(ch[x][0]);
        if(ch[x][1]) reverse(ch[x][1]);
        rev[x]=0;
    }
    if(same[x]){
        if(ch[x][0]) replace(ch[x][0], w[x]);
        if(ch[x][1]) replace(ch[x][1], w[x]);
        same[x]=0;
    }
}

void rotate(int x){
    int y = fa[x], kind = ch[y][1] == x;
    pushdown(y), pushdown(x);
    ch[y][kind] = ch[x][!kind];
    fa[ch[y][kind]] = y;
    ch[x][!kind] = y;
    fa[x] = fa[y];
    fa[y] = x;
    ch[fa[x]][ch[fa[x]][1] == y] = x;
    pushup(y), pushup(x);
}

void splay(int x, int goal)
{
    while(fa[x] != goal)
    {
        int y = fa[x], z = fa[y];
        if(z == goal) rotate(x);
        else if((ch[y][1] == x) == (ch[z][1] == y)) rotate(y), rotate(x);
        else rotate(x), rotate(x);
    }
    if(goal == 0) root = x;
}

int find_k(int x, int k){
    pushdown(x);
    if(siz[ch[x][0]]==k-1) return x;
    if(siz[ch[x][0]]>k-1) return find_k(ch[x][0], k);
    else return find_k(ch[x][1], k-siz[ch[x][0]]-1);
}

void build(int l, int r, int rt){
    int mid = (l+r)/2;
    w[rt]=a[mid];
    if(l==r){
        sum[rt]=lmax[rt]=rmax[rt]=ans[rt]=w[rt];
        siz[rt]=1;
        return;
    }
    if(l<mid){
        ch[rt][0]=newnode();
        fa[ch[rt][0]]=rt;
        build(l,mid-1,ch[rt][0]);
    }
    if(mid<r){
        ch[rt][1]=newnode();
        fa[ch[rt][1]]=rt;
        build(mid+1,r,ch[rt][1]);
    }
    pushup(rt);
}

int Query(int l, int num)
{
    int x = find_k(root, l);
    splay(x, 0);
    int y = find_k(ch[x][1], num+1);
    splay(y, x);
    return sum[ch[y][0]];
}

void Insert(int l, int num)
{
    for(int i=1; i<=num; i++) scanf("%d", &a[i]);
    int x = find_k(root, l+1);
    splay(x, 0);
    int y = find_k(ch[x][1], 1);
    splay(y, x);
    ch[y][0] = newnode();
    fa[ch[y][0]] = y;
    build(1, num, ch[y][0]);
    pushup(y);
    pushup(x);
}

void Erase(int x){
    if(!x) return ;
    st[++top]=x;
    if(ch[x][0]) Erase(ch[x][0]);
    if(ch[x][1]) Erase(ch[x][1]);
}

void Delete(int l, int num){
    int x = find_k(root, l);
    splay(x, 0);
    int y = find_k(ch[x][1], num+1);
    splay(y, x);
    Erase(ch[y][0]);
    fa[ch[y][0]]=0;
    ch[y][0]=0;
    pushup(y);
    pushup(x);
}

void Reverse(int l, int num){
    int x = find_k(root, l);
    splay(x, 0);
    int y = find_k(ch[x][1], num+1);
    splay(y, x);
    reverse(ch[y][0]);
    pushup(y);
    pushup(x);
}

void Replace(int l, int num, int d){
    int x = find_k(root, l);
    splay(x, 0);
    int y = find_k(ch[x][1], num+1);
    splay(y, x);
    replace(ch[y][0], d);
    pushup(y);
    pushup(x);
}

int main(){
    lmax[0] = rmax[0] = ans[0] = -inf;
    tot = 2;
    root = 1;
    fa[1] = 0;
    siz[1] = 2;
    ch[1][1] = 2;
    w[1] = sum[1] = lmax[1] = rmax[1] = -inf;
    fa[2] = 1;
    siz[2] = 1;
    w[2] = sum[2] = lmax[2] = rmax[2] = -inf;
    int n, T;
    scanf("%d%d", &n, &T);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    ch[2][0] = newnode(); fa[ch[2][0]] = 2;
    build(1, n, ch[2][0]);
    pushup(2);
    pushup(1);
    while(T--){
        int x, y, z;
        scanf("%s", s);
        if(s[2] == 'X'){
            printf("%d\n", ans[root]);
        }
        if(s[0] == 'G'){
            scanf("%d%d", &x, &y);
            printf("%d\n", Query(x, y));
        }
        if(s[0] == 'I'){
            scanf("%d%d", &x,&y);
            Insert(x, y);
        }
        if(s[0] == 'D'){
            scanf("%d%d", &x,&y);
            Delete(x, y);
        }
        if(s[0] == 'R'){
            scanf("%d%d", &x,&y);
            Reverse(x, y);
        }
        if(s[4] == '-'){
            scanf("%d%d%d", &x,&y,&z);
            Replace(x, y, z);
        }
    }
    return 0;
}