AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=1500
[前言]
据说没打这题就相当于没打过Splay，这题简直就是让你内心崩溃的...
这题是一道综合味很强的题，初学者不要贸然尝试...先做些简单一点的[跟着笔者的步伐走...做一做3224、3223、1251、1014这种类型]，最好也要有一定的线段树lazy_tag基础。
[分析]
首先数据范围没写...但是前人告诉你必须要用Splay[写在source里了]
所以说这题肯定有一个很大的数据范围...
而这题中需要支持的操作大多是区间上的操作，也是有很多下传标记和求区间和与区间最值的，同时有翻转操作[似乎支持这些的也只有伸展树了...]。
确定了总的方向，再具体看看操作：
１．预处理出一开始给你的数列。[和平常一样构造就好，这个部分最需要注意的就是下标这种细节了]
２．在一个位置后添加一段序列，和以前加一个数字的操作很像，但是我们要像之前处理初始序列一样将这棵子树先构造出来，再将根接到位置上。
３．删除一段序列，以往的题，只需要将这棵子树与父节点的关系弄掉即可，这题因为点数要求多[每次删一段，加一段]，所以还需要回收这些删除的点，具体方法[暴力一个个点的下去，把他们的编号放进墓地里]。
４．修改一段序列为一个定值，和线段树的强制赋值一样处理就好了。
５．翻转一段区间，翻转标记的处理，具体见BZOJ3223。
６．求一段区间的和，每次上传的时候需要更新一下。
７．求全局中的最大子串，这个稍稍难想一点。
同样的因为上面的这种设置方法，我们在进行翻转操作的时候记得也要翻转lmax,rmax
当然具体的细节问题，给你们自己去调试咯...
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm> using namespace std; inline int in(){
int x=,f=;char ch=getchar();
while((ch>'' || ch<'') && ch!='-') ch=getchar();
if(ch=='-') f=-,ch=getchar();
while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return x*f;
} const int maxn=;
const int INF=0x3f3f3f3f; struct Node{
int ch[],f; //child[2],father
int sz,dt,sm; //size,data,sum
int lx,rx,mx; //left_max,right_max,Max bool rv,pt; //rev,paint
}s[maxn]; int n,q,rt,tot1;
int st[maxn],tot2;//墓地和容量
int a[maxn];
char ch[]; void NewNode(int &r,int father,int k){
if(tot2) r=st[tot2--];//优先选择墓地里的
else r=++tot1;
s[r].f=father;
s[r].ch[]=s[r].ch[]=;
s[r].dt=s[r].sm=k;
s[r].rv=s[r].pt=;
s[r].lx=s[r].rx=s[r].mx=k;
s[r].sz=;
} //应用并下传rev标记，记得要旋转左右最值
void Update_Rev(int x){
if(!x) return;
swap(s[x].ch[],s[x].ch[]);
swap(s[x].lx,s[x].rx);
s[x].rv^=;
} //应用并下传paint标记
void Update_Same(int x,int v){
if(!x) return;
s[x].dt=v;
s[x].sm=v*s[x].sz;
s[x].lx=s[x].rx=s[x].mx=max(v,v*s[x].sz);
s[x].pt=;
} //更新节点信息
void push_up(int x){
int l=s[x].ch[],r=s[x].ch[];
s[x].sz=s[l].sz+s[r].sz+;
s[x].sm=s[l].sm+s[r].sm+s[x].dt;
s[x].lx=max(s[l].lx,s[l].sm+s[x].dt+max(,s[r].lx));
s[x].rx=max(s[r].rx,s[r].sm+s[x].dt+max(,s[l].rx));
s[x].mx=max(,s[l].rx)+s[x].dt+max(,s[r].lx);
s[x].mx=max(s[x].mx,max(s[l].mx,s[r].mx));
} void push_down(int x){
if(s[x].pt){
Update_Same(s[x].ch[],s[x].dt);
Update_Same(s[x].ch[],s[x].dt);
s[x].pt=;
}
if(s[x].rv){
Update_Rev(s[x].ch[]);
Update_Rev(s[x].ch[]);
s[x].rv=;
}
} void Build(int &x,int l,int r,int father){
if(l>r) return;
int mid=(l+r)>>;
NewNode(x,father,a[mid]);
Build(s[x].ch[],l,mid-,x);
Build(s[x].ch[],mid+,r,x);
push_up(x);
} void Init(){
rt=tot1=tot2=;
s[rt].ch[]=s[rt].ch[]=s[rt].sz=s[rt].f=;
s[rt].pt=s[rt].rv=s[rt].sm=s[rt].dt=;
s[rt].lx=s[rt].rx=s[rt].mx=-INF;
NewNode(rt,,-);
NewNode(s[rt].ch[],rt,-);
for(int i=;i<n;i++)
scanf("%d",&a[i]);
Build(s[s[rt].ch[]].ch[],,n-,s[rt].ch[]);
push_up(s[rt].ch[]);
push_up(rt);
} void Rotate(int x,int k){
int y=s[x].f;
s[x].f=s[y].f;
if(s[y].f){
if(y==s[s[y].f].ch[])
s[s[y].f].ch[]=x;
else
s[s[y].f].ch[]=x;
}
s[y].ch[k]=s[x].ch[k^];
if(s[x].ch[k^]) s[s[x].ch[k^]].f=y;
s[x].ch[k^]=y;s[y].f=x;
push_up(y),push_up(x);
} void Splay(int x,int gf){
int y;
while(s[x].f!=gf){
y=s[x].f;
if(s[y].f==gf){
if(x==s[y].ch[]) Rotate(x,); else Rotate(x,);}
else{
int z=s[y].f;
if(y==s[z].ch[]){
if(x==s[y].ch[]) Rotate(y,),Rotate(x,); else Rotate(x,),Rotate(x,);}
else{
if(x==s[y].ch[]) Rotate(y,),Rotate(x,); else Rotate(x,),Rotate(x,);}
}
}
if(!gf) rt=x;
} int Get_kth(int k){
int p=rt;
while(p){
push_down(p);
if(k<=s[s[p].ch[]].sz) p=s[p].ch[];
else{
k-=s[s[p].ch[]].sz;
if(k==) return p;
k--;p=s[p].ch[];
}
}
} //在第pos个数后面插入tot个数
void Insert(int pos,int tot){
for(int i=;i<tot;i++) scanf("%d",&a[i]);
int x1=Get_kth(pos+),x2=Get_kth(pos+);
Splay(x1,),Splay(x2,x1);
Build(s[x2].ch[],,tot-,x2);
push_up(x2),push_up(x1);
} //删除子树
void erase(int x){
if(!x) return; st[++tot2]=x;//删除的节点需要回收进墓地
erase(s[x].ch[]),erase(s[x].ch[]);
} //从第pos个数开始连续删除tot个数
void Delete(int pos,int tot){
int x1=Get_kth(pos),x2=Get_kth(pos+tot+);
Splay(x1,),Splay(x2,x1);
erase(s[x2].ch[]);
s[s[x2].ch[]].f=;
s[x2].ch[]=;
push_up(x2),push_up(x1);
} //将从第pos个数开始的连续的tot个数染色成c
void Make_Same(int pos,int tot,int c){
int x1=Get_kth(pos),x2=Get_kth(pos+tot+);
Splay(x1,),Splay(x2,x1);
Update_Same(s[x2].ch[],c);
push_up(x2),push_up(x1);
} //将第pos个数开始的连续tot个数进行反转
void Reverse(int pos,int tot){
int x1=Get_kth(pos),x2=Get_kth(pos+tot+);
Splay(x1,),Splay(x2,x1);
Update_Rev(s[x2].ch[]);
push_up(x2),push_up(x1);
} //得到第pos个数开始的tot个数的和
int Get_Sum(int pos,int tot){
int x1=Get_kth(pos),x2=Get_kth(pos+tot+);
Splay(x1,),Splay(x2,x1);
return s[s[x2].ch[]].sm;
} //得到第pos个数开始的tot个数中最大的子段和
int Get_MaxSum(int pos,int tot){
int x1=Get_kth(pos),x2=Get_kth(pos+tot+);
Splay(x1,),Splay(x2,x1);
return s[s[x2].ch[]].mx;
} int main(){
#ifndef ONLINE_JUDGE
freopen("1500.in","r",stdin);
freopen("1500.out","w",stdout);
#endif
int L,tot,x; n=in();q=in();
Init();
while(q--){
scanf("%s",ch);
if(ch[]=='I')
L=in(),tot=in(),Insert(L,tot);
else if(ch[]=='D')
L=in(),tot=in(),Delete(L,tot);
else if(ch[]=='M'){
if(ch[]=='K')
L=in(),tot=in(),x=in(),Make_Same(L,tot,x);
else
printf("%d\n",Get_MaxSum(,s[rt].sz-));
}
else if(ch[]=='R')
L=in(),tot=in(),Reverse(L,tot);
else
L=in(),tot=in(),printf("%d\n",Get_Sum(L,tot));
}
return ;
}