题目：BZOJ1500、洛谷P2042、Vijos P1835、codevs1758。
题目大意：
给你一个数列，实现以下操作。
解题思路：
非旋Treap维护数列即可。
前面5个都是基本的平衡树序列操作（第5个维护一个区间和即可）。
第6个要求最大子段和，则我们需要维护以当前节点为子树的子段和，当前子树的最大前缀和和最大后缀和，才能转移出正确的最大子段和。（具体如何维护详见代码）
对于旋转操作，需要把前缀和后缀交换一下。
还有要注意：
1. 内存不能开太大，会MLE，要回收被删除的节点。
2. 插入时不要一个一个merge，先按照笛卡尔树的建树方式建树（O(n)），然后直接merge根即可。
C++ Code：
#include<bits/stdc++.h>
inline int max(int a,int b){return a>b?a:b;}
inline void swap(int& a,int& b){int c=a;a=b,b=c;}
inline int readint(){
int c=getchar(),d=0,b=0;
for(;!isdigit(c);c=getchar())b=c=='-';
for(;isdigit(c);c=getchar())d=(d<<3)+(d<<1)+(c^'0');
return b?-d:d;
}
struct node{
int ls,rs,s,lm,rm,sm,smx,rot,r,tag,sz;
inline void Cng(int val){
s=val;
sm=sz*val;
lm=rm=max(sm,0);
smx=max(sm,s);
tag=1;
}
inline void rev(){
swap(ls,rs);
swap(lm,rm);
rot^=1;
}
}a[500005];
struct Memory_pool{
int p[500005],top;
Memory_pool(){
for(int i=1;i<=500004;++i)p[i]=i;
top=500004;
}
inline int New(){return p[top--];}
inline void Del(int x){p[++top]=x;}
}P;
int n,m,rt,sta[500005],top=0;
inline void pushdown(int x){
if(a[x].rot){
a[x].rot=0;
if(a[x].ls)a[a[x].ls].rev();
if(a[x].rs)a[a[x].rs].rev();
}
if(a[x].tag){
a[x].tag=0;
if(a[x].ls)a[a[x].ls].Cng(a[x].s);
if(a[x].rs)a[a[x].rs].Cng(a[x].s);
}
}
inline void update(int x){
int ls=a[x].ls,rs=a[x].rs,s=a[x].s;
if(ls&&rs){
a[x].sz=a[ls].sz+a[rs].sz+1;
a[x].sm=a[ls].sm+a[rs].sm+s;
a[x].smx=max(a[ls].smx,a[rs].smx);
a[x].smx=max(a[x].smx,a[ls].rm+s+a[rs].lm);
a[x].lm=max(a[ls].lm,a[ls].sm+s+a[rs].lm);
a[x].rm=max(a[rs].rm,a[rs].sm+s+a[ls].rm);
}else
if(ls){
a[x].sz=a[ls].sz+1;
a[x].sm=a[ls].sm+s;
a[x].smx=max(a[ls].smx,a[ls].rm+s);
a[x].lm=max(a[ls].lm,a[ls].sm+s);
a[x].rm=max(a[ls].rm+s,0);
}else
if(rs){
a[x].sz=a[rs].sz+1;
a[x].sm=a[rs].sm+s;
a[x].smx=max(a[rs].smx,a[rs].lm+s);
a[x].rm=max(a[rs].rm,a[rs].sm+s);
a[x].lm=max(a[rs].lm+s,0);
}else{
a[x].sz=1;
a[x].sm=a[x].smx=s;
a[x].lm=a[x].rm=max(s,0);
}
}
int build(int n){
int x,pre;
for(int i=1;i<=n;++i){
int f=readint();
int ff=max(f,0);
a[x=P.New()]=(node){0,0,f,ff,ff,f,f,0,rand(),0,1};
for(pre=0;top&&a[sta[top]].r>a[x].r;--top)update(pre=sta[top]);
if(top)a[sta[top]].rs=x;
a[sta[++top]=x].ls=pre;
}
while(top)update(sta[top--]);
return sta[1];
}
void split(int u,int k,int& x,int& y){
if(!k){
x=0,y=u;
return;
}
if(k==a[u].sz){
x=u,y=0;
return;
}
pushdown(u);
if(a[a[u].ls].sz>=k)split(a[u].ls,k,x,a[u].ls),y=u;else
split(a[u].rs,k-a[a[u].ls].sz-1,a[u].rs,y),x=u;
update(u);
}
int merge(int x,int y){
if(x)pushdown(x);
if(y)pushdown(y);
if(!x||!y)return x|y;
if(a[x].r<a[y].r){
a[x].rs=merge(a[x].rs,y);
update(x);
return x;
}
a[y].ls=merge(x,a[y].ls);
update(y);
return y;
}
void dispose(int now){
if(!now)return;
dispose(a[now].ls);
dispose(a[now].rs);
P.Del(now);
}
int main(){
n=readint(),m=readint();
a[0]=(node){0,0,0,0,0,0,0,0,0,0,0};
srand(20170607);
rt=build(n);
while(m--){
static char s[100];
int tot;
scanf("%s",s);
if(s[0]=='I'){
tot=readint();int rtn=build(readint()),x,y;
split(rt,tot,x,y);
rt=merge(merge(x,rtn),y);
}else
if(s[0]=='D'){
tot=readint(),n=readint();
int x,y,z;
split(rt,tot-1,x,y);
split(y,n,y,z);
dispose(y);
rt=merge(x,z);
}else
if(s[0]=='M'&&s[2]=='K'){
tot=readint(),n=readint();
int x,y,z;
split(rt,tot-1,x,y);
split(y,n,y,z);
a[y].Cng(readint());
rt=merge(merge(x,y),z);
}else
if(s[0]=='R'){
tot=readint(),n=readint();
int x,y,z;
split(rt,tot-1,x,y);
split(y,n,y,z);
a[y].rev();
rt=merge(merge(x,y),z);
}else
if(s[0]=='G'){
tot=readint(),n=readint();
int x,y,z;
split(rt,tot-1,x,y);
split(y,n,y,z);
printf("%d
",a[y].sm);
rt=merge(merge(x,y),z);
}else printf("%d
",a[rt].smx);
}
return 0;
}