真的是太弱了TAT。。。光是把代码码出来就花了3h。。还调了快1h才弄完T_T
号称考你会不会splay（当然通过条件是1h内AC。。吓傻）。。。
黄学长的题解：http://hzwer.com/2841.html
当然了蒟蒻的splay模板全部都是借（抄）鉴（袭）黄学长的。。。。
主要是注意任何对子树的修改一定要记得pushup一定要记得pushup一定要记得pushup。。。计算最大子段和和bzoj1858一个姿势，就是维护子树的最大子段和，从左和从右开始的最大子段和（当然了平衡树和线段树在这里还是有点区别的）；
对于修改和翻转可以打懒标记。。。插入的话可以先把要插入的数建出一颗splay树，然后把新树和原来的树连起来；
为了避免判断区间边界啊什么的可以多建两个边界节点。。。
据说要加上垃圾回收，这样的话还要新开一个id数组用来存节点的编号，那样的话数组开到50w就可以了。。
如果不要垃圾回收的话，删除时把对应区间的子树与原来的树断开连接就好了，垃圾回收还得把要砍掉的子树里面的节点遍历重置。。。oj上没写数据范围让人感觉有点虚。。
#include<stdio.h>
#include<math.h>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=;
const int maxn=;//题目又没说数据范围= =//经测试加了垃圾优化开50w就好了= =
struct zs{
int c[],fa,mx,lmx,rmx,val,size,sum;
bool change,rev;
}tree[maxn];
queue<int>q;
int a[maxn],id[maxn];
char iid[];
int i,j,k,n,m,cnt,tot,x,c,root;
void update(int now){
int l=tree[now].c[],r=tree[now].c[];
tree[now].size=tree[l].size+tree[r].size+;
tree[now].sum=tree[l].sum+tree[r].sum+tree[now].val;
tree[now].mx=max(tree[l].mx,tree[r].mx);
tree[now].mx=max(tree[now].mx,tree[l].rmx+tree[now].val+tree[r].lmx);
tree[now].lmx=max(tree[l].lmx,tree[l].sum+tree[now].val+tree[r].lmx);
tree[now].rmx=max(tree[r].rmx,tree[r].sum+tree[now].val+tree[l].rmx);
}
void deal(int now,bool change,bool rev,int val){
if(change){
tree[now].change=;
tree[now].val=val;
tree[now].sum=tree[now].size*val;
if(val>)
tree[now].mx=tree[now].lmx=tree[now].rmx=tree[now].sum;
else tree[now].mx=val,tree[now].lmx=tree[now].rmx=;
}
else//如果整段覆盖了翻不翻转都一样
if(rev){
tree[now].rev^=;
// printf("! %d %d %d\n",now,tree[now].c[0],tree[now].c[1]);
swap(tree[now].c[],tree[now].c[]);
swap(tree[now].lmx,tree[now].rmx);
}
}
void pushdown(int now){
int l=tree[now].c[],r=tree[now].c[];
if(l)deal(l,tree[now].change,tree[now].rev,tree[now].val);
if(r)deal(r,tree[now].change,tree[now].rev,tree[now].val);
tree[now].change=tree[now].rev=;
}
void build(int l,int r,int premid){
int now,mid,fa;
if(l>r)return;
mid=(l+r)>>;
fa=id[premid];now=id[mid];//本来id[i]==i,但因为垃圾回收。。。
if(mid<premid)tree[fa].c[]=now;else tree[fa].c[]=now;
tree[now].fa=fa;
tree[now].val=a[mid];
if(l<r){
build(l,mid-,mid);build(mid+,r,mid);
update(now);
}else{
// printf(" !%d %d\n",now,tree[now].val);
tree[now].size=;
tree[now].mx=tree[now].sum=tree[now].val;
if(tree[now].val>)tree[now].lmx=tree[now].rmx=tree[now].mx;
else tree[now].lmx=tree[now].rmx=;
}
// printf("! %d %d %d %d %d %d %d %d\n",now,tree[now].c[0],tree[now].c[1],tree[now].mx,tree[now].lmx,tree[now].rmx,tree[now].change,tree[now].rev);
}
void rotate(int now,int&root){
int fa,gfa,l,r;
fa=tree[now].fa;gfa=tree[fa].fa;
if(fa==root)root=now;
else tree[gfa].c[tree[gfa].c[]!=fa]=now;
if(tree[fa].c[]==now)l=;else l=;
r=l^;
tree[now].fa=gfa;tree[fa].fa=now;
tree[fa].c[l]=tree[now].c[r];tree[now].c[r]=fa;
tree[tree[fa].c[l]].fa=fa;
update(fa);update(now);
}
void splay(int now,int&root){
int fa,gfa;
while(now!=root){
fa=tree[now].fa;gfa=tree[fa].fa;
if(fa!=root)
if((tree[fa].c[]==now)^(tree[gfa].c[]==fa))rotate(now,root);
else rotate(fa,root);
rotate(now,root);
}
}
int find(int now,int k){
if(tree[now].change||tree[now].rev)pushdown(now);
int l=tree[now].c[];
if(k<=tree[l].size)return find(l,k);
else if(k==tree[l].size+)return now;
else return find(tree[now].c[],k-tree[l].size-);
}
void ins(int pos,int tot){
// int now=find(root,pos+1);
for(int i=;i<=tot;i++)scanf("%d",&a[i]);
for(int i=;i<=tot;i++)
if(!q.empty())id[i]=q.front(),q.pop();
else id[i]=++cnt;
int troot=id[(tot+)>>];
build(,tot,);
int x=find(root,pos+),y=find(root,pos+);
splay(x,root);splay(y,tree[x].c[]);
tree[y].c[]=troot;tree[troot].fa=y;
update(y);update(x);
// printf(" !%d\n",root);
}
void recover(int &now){
tree[now].fa=;
if(tree[now].c[])recover(tree[now].c[]);
if(tree[now].c[])recover(tree[now].c[]);
q.push(now);
tree[now].change=tree[now].rev=;
now=;
}
void del(int pos,int tot){
// int now=find(root,pos+1);
int x=find(root,pos),y=find(root,pos+tot+);
splay(x,root);splay(y,tree[x].c[]);
// int z=tree[y].c[0];tree[y].c[0]=0;
recover(tree[y].c[]);
update(y);update(x);//要更新祖先TAT
}
void bilibili(int pos,int tot,int change,int rev,int val){//处理修改&&翻转
int x=find(root,pos),y=find(root,pos+tot+);
splay(x,root);splay(y,tree[x].c[]);
// printf(" ! %d %d %d %d\n",tree[y].c[0],change,rev,val);
deal(tree[y].c[],change,rev,val);
update(y);update(x);//也要更新祖先TAT
// printf("! %d %d\n",y,x);
}
void getsum(int pos,int tot){
// int now=find(root,pos+1);
int x=find(root,pos),y=find(root,pos+tot+);
splay(x,root);splay(y,tree[x].c[]);
int z=tree[y].c[];
printf("%d\n",tree[z].sum);
}
int main(){
scanf("%d%d",&n,&m);
for(i=;i<=n;i++)scanf("%d",&a[i+]);
a[]=a[n+]=-inf;
for(i=;i<=n+;i++)id[i]=i;
tree[].mx=-inf;
root=(n++)>>;cnt=n+;
build(,n+,);
// for(i=1;i<=cnt;i++)printf(" %d %d %d %d %d %d\n",i,tree[i].c[0],tree[i].c[1],tree[i].mx,tree[i].lmx,tree[i].rmx);
for(i=;i<=m;i++){
scanf("%s",iid);
if(iid[]=='S')scanf("%d%d",&x,&tot),ins(x,tot);
else if(iid[]=='L')scanf("%d%d",&x,&tot),del(x,tot);
else if(iid[]=='K')scanf("%d%d%d",&x,&tot,&c),bilibili(x,tot,,,c);
else if(iid[]=='V')scanf("%d%d",&x,&tot),bilibili(x,tot,,,);
else if(iid[]=='T')scanf("%d%d",&x,&tot),getsum(x,tot);
else if(iid[]=='X')printf("%d\n",tree[root].mx);
//if(i==4)
// for(int i=1;i<=cnt;i++)printf(" %d %d %d %d %d %d %d %d\n",i,tree[i].c[0],tree[i].c[1],tree[i].mx,tree[i].lmx,tree[i].rmx,tree[i].change,tree[i].rev);
// return 233;
}
return ;
}
//连续几天写到的题目都没有数据范围是什么鬼。。。
//至于读入的时候少打一个%d这种错显然只有傻叉才会犯的啊TAT
//变量名太长的悲剧。。。把几个过程缩成一个结果代码量还是别人的两倍T_T
感觉自己还不会splay。。。果然是太弱了。。也许过一阵子再来写这题效果会好点= =
2015.8.1:4h
2015.8.6:2h ： 注意删点的时候那些新建节点时没有初始化的信息都要初始化，
2016.1.6：4h+。。TAT。。太久没玩懒标记结果卡了一晚上+一节电脑课。。。要好好想一下什么时候更新本节点的信息。。