http://www.lydsy.com/JudgeOnline/problem.php?id=1500 (题目链接)
题意
要求维护数列，操作有区间删除，区间插入，区间反转，区间修改，区间求和，求最大连续子段。
Solution
愿有生之年再也不写splay。代码模的hzwer。
2017.3.24：upd了一下代码。
代码
// baoj1500
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define inf (1ll<<30)
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
inline int gi() {
int x=0,f=1;char ch=getchar();
while (ch<'0' || ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
} const int maxn=1000010;
int a[maxn],fa[maxn],n,m,rt,sz;
char ch[30];
struct node {
int lx,rx,mx,val,sum,size,son[2],rev,tag;
int& operator [] (int x) {return son[x];}
}tr[maxn];
queue<int> q; void pushup(int k) {
int l=tr[k][0],r=tr[k][1];
tr[k].size=tr[l].size+tr[r].size+1; //子树大小
tr[k].sum=tr[l].sum+tr[r].sum+tr[k].val; //区间和
tr[k].mx=max(tr[l].mx,tr[r].mx); //最大连续段
tr[k].mx=max(tr[k].mx,tr[l].rx+tr[k].val+tr[r].lx);
tr[k].lx=max(tr[l].lx,tr[l].sum+tr[k].val+tr[r].lx); //左端最大区间
tr[k].rx=max(tr[r].rx,tr[r].sum+tr[k].val+tr[l].rx); //右端最大区间
}
void pushdown(int k) {
int l=tr[k][0],r=tr[k][1];
if (tr[k].tag) {
tr[k].tag=tr[k].rev=0; //赋成同一个值,反不反转都一样
if (l) tr[l].tag=1,tr[l].val=tr[k].val,tr[l].sum=tr[l].val*tr[l].size;
if (r) tr[r].tag=1,tr[r].val=tr[k].val,tr[r].sum=tr[r].val*tr[r].size;
if (tr[k].val>=0) {
if (l) tr[l].lx=tr[l].rx=tr[l].mx=tr[l].sum;
if (r) tr[r].lx=tr[r].rx=tr[r].mx=tr[r].sum;
}
else {
if (l) tr[l].lx=tr[l].rx=0,tr[l].mx=tr[l].val;
if (r) tr[r].lx=tr[r].rx=0,tr[r].mx=tr[r].val;
}
}
if (tr[k].rev) {
tr[k].rev^=1,tr[l].rev^=1,tr[r].rev^=1;
swap(tr[l].lx,tr[l].rx),swap(tr[l][0],tr[l][1]);
swap(tr[r].lx,tr[r].rx),swap(tr[r][0],tr[r][1]);
}
}
void rotate(int x,int &k) {
int y=fa[x],z=fa[y],l,r;
l=tr[y][1]==x;r=l^1;
if (y==k) k=x;
else tr[z][tr[z][1]==y]=x;
fa[tr[x][r]]=y;fa[y]=x;fa[x]=z;
tr[y][l]=tr[x][r];tr[x][r]=y;
pushup(y),pushup(x); //注意更新顺序
}
void splay(int x,int &k) {
while (x!=k) {
int y=fa[x],z=fa[y];
if (y!=k) {
if ((tr[y][0]==x) ^ (tr[z][0]==y)) rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int find(int k,int x) {
pushdown(k);
if (tr[tr[k][0]].size+1==x) return k;
else if (x<=tr[tr[k][0]].size) return find(tr[k][0],x);
else return find(tr[k][1],x-tr[tr[k][0]].size-1);
}
void recycle(int k) { //清空
if (tr[k][0]) recycle(tr[k][0]);
if (tr[k][1]) recycle(tr[k][1]);
q.push(k);tr[k][0]=tr[k][1]=tr[k].tag=tr[k].rev=0; //节点回收入队,重复利用
}
int split(int l,int r) { //抠出区间
int x=find(rt,l),y=find(rt,r+2);
splay(x,rt),splay(y,tr[x][1]);
return tr[y][0];
}
int query(int l,int r) {
return tr[split(l,r)].sum;
}
void modify(int l,int r,int val) {
int x=split(l,r),y=fa[x];
tr[x].val=val;tr[x].tag=1;tr[x].sum=tr[x].size*val;
if (val>=0) tr[x].lx=tr[x].rx=tr[x].mx=tr[x].sum;
else tr[x].lx=tr[x].rx=0,tr[x].mx=val;
pushup(y),pushup(fa[y]);
}
void reverse(int l,int r) {
int x=split(l,r),y=fa[x];
if (!tr[x].tag) {
tr[x].rev^=1;
swap(tr[x][0],tr[x][1]);
swap(tr[x].lx,tr[x].rx);
pushup(y),pushup(fa[y]);
}
}
void erase(int l,int r) {
int x=split(l,r),y=fa[x];
recycle(x);tr[y][0]=0;
pushup(y),pushup(fa[y]);
}
void build(int &k,int l,int r,int f) {
int mid=(l+r)>>1;
if (!q.empty()) k=q.front(),q.pop();else k=++sz;
tr[k].sum=tr[k].val=a[mid];fa[k]=f;
tr[k].lx=tr[k].rx=tr[k].mx=max(0,a[mid]);
if (l<mid) build(tr[k][0],l,mid-1,k);
if (r>mid) build(tr[k][1],mid+1,r,k);
pushup(k);
}
void insert(int k,int tot) {
for (int i=1;i<=tot;i++) scanf("%d",&a[i]);
int x,y,z;
build(z,1,tot,0);
x=find(rt,k+1),y=find(rt,k+2); //因为有"哨兵",实际上是find k,k+1
splay(x,rt),splay(y,tr[x][1]); //因为k,k+1,所以tr[y][0]为空
fa[z]=y;tr[y][0]=z;pushup(y),pushup(x); //注意pushup的顺序
}
int main() {
n=gi(),m=gi();
tr[0].mx=a[1]=a[n+2]=-inf;
for (int i=1;i<=n;i++) a[i+1]=gi();
build(rt,1,n+2,0);
while (m--) {
int k,tot,val;scanf("%s",ch);
if (ch[0]!='M' || ch[2]!='X') k=gi(),tot=gi();
if (ch[0]=='I') insert(k,tot);
else if (ch[0]=='D') erase(k,k+tot-1);
else if (ch[0]=='M') {
if (ch[2]=='X') printf("%d\n",tr[rt].mx);
else scanf("%d",&val),modify(k,k+tot-1,val);
}
else if (ch[0]=='R') reverse(k,k+tot-1);
else if (ch[0]=='G') printf("%d\n",query(k,k+tot-1));
}
return 0;
}