P2042 [NOI2005]维护数列
数列区间和，最大子列和（必须不为空），支持翻转、修改值、插入删除。
练码力的题，很毒瘤。个人因为太菜了，对splay极其生疏，犯了大量错误，在此记录，望以后一定要多多回顾！！！！
（以后复习splay板子干脆就这道题算了）
1.审题问题（明明就是题目没说清楚的说） 最大子序列和不能为空，也就是必有数，有负数你也得选。
2.思路方面：
关于插入：在要插入的地方通过splay把他腾出空当不就行了。即把k旋到根，k+1旋到右儿子，则k+1左儿子必为空，此时把数列二分构建成一颗平衡的树，挂上去就行了。
关于删除：同上，把删除区间搞出来，把他咔掉。但是这题卡空间，找题目意思最多会插入4500000个数，每个点还要维护接近10个变量，肯定炸。所以要将冗余转态的节点，也就是删除的节点回收扔到队列里去，下次插入时可以在拿来用。删除时要遍历目标子树所有节点回收，但因为总共只会有4500000个数被删掉，所以累计也就几百万此操作，不影响复杂度。回收机制其实是跟别人学的，细节还见代码。
关于区间修改：打标记。不用担心边界两个点被下传到，本来操作就不会覆盖到他们。pushdown时如果有该标记优于翻转标记下传，因为其已无意义。
关于区间翻转：打标记。注意因为之前文艺平衡树那题受人误导，翻转标记也最好打上之后像线段树一样及时更新，具体原因待会讲。
关于求和：不说了吧。
关于最大子列和：这个是一个新的思路。分治。具体可以看下这题，类似的，方程看题解区，不写了。
3.错误列举
- 由于最大子列和不为空，所以细节有所改动。维护的区间最大前缀、后缀和还可以是0，反正他也不是答案，而且也方便更新总最大连续和。最大连续和在叶节点上就只能是该值本身，这保证不为空。既然这样，对照pushdown的细节会发现，推父亲maxsum，比较孩子大小时，孩子有时由于是空的所以相当于返回了T[0].ms,为了不干扰，必把0节点sum设成-inf。同理，边界两点也应把ms设成-inf。
- 毕竟码量有点大，实在很容易打错，这次出现了两个typo。copy时还当多多注意。这个我也没办法。
- 统一修改的标记初始值不可为0，这个想想就知道了，所以设个极小值。
- 翻转的标记一定要如同其他标记一样打下时立刻进行，不要等下次访问在更新信息并下传。文艺平衡树那题没问题，但这题如果打下rev标记后不及时翻转，待下次访问到时再传到儿子，由于错误的机制导致儿子不会立刻翻转。而这题由于维护最大序列和的需求，要维护左端连续和右端连续最大和，试想当我的儿子的这些信息没有被更新（翻转），我自己用了没更新前的左/右最大连续和，不是会出错？这点在这题尤其明显，我rev不及时翻转，ls和rs就不会及时更新。后果可想而知。
- splay记得操作后经常pushup两次
#include<bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x <<endl
using namespace std;
typedef long long ll;
template<typename T>inline T _min(T A,T B){return A>B?B:A;}
template<typename T>inline T _max(T A,T B){return A<B?B:A;}
template<typename T>inline T _max(T A,T B,T C){return _max(_max(A,B),C);}
template<typename T>inline void _swap(T&a,T&b){a^=b^=a^=b;}
template<typename T>inline int read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+c-'',c=getchar();return f?x=-x:x;
}
const int N=+,INF=5e8;
struct tree{
int ch[],f,siz,val,sam,rev,sum,ls,rs,ms;
}T[N];
queue<int> q;
int id[N],A[N];
int n,m,tot,rt,len; inline int dir(int x){return T[T[x].f].ch[]==x;}
inline void pushup(int x){//MISTAKE:the max sum can't be empty.
int l=T[x].ch[],r=T[x].ch[];
T[x].siz=T[l].siz+T[r].siz+;
T[x].sum=T[l].sum+T[r].sum+T[x].val;
T[x].ls=_max(T[l].ls,T[l].sum+T[x].val+T[r].ls);
T[x].rs=_max(T[r].rs,T[r].sum+T[x].val+T[l].rs);//MISTAKE occured when copying.
T[x].ms=_max(T[l].ms,T[r].ms,T[l].rs+T[x].val+T[r].ls);
// dbg(x),dbg(l),dbg(r),dbg(T[x].sum),dbg(T[x].siz);
}
inline void pushdown(int x){
int l=T[x].ch[],r=T[x].ch[];
if(T[x].sam^(-INF)){
T[l].val=T[r].val=T[l].sam=T[r].sam=T[x].sam;
T[l].sum=T[l].siz*T[l].sam,T[r].sum=T[r].siz*T[r].sam;
if(T[x].sam>)T[l].ls=T[l].rs=T[l].ms=T[l].sum,T[r].ls=T[r].rs=T[r].ms=T[r].sum;
else T[l].ls=T[l].rs=T[r].ls=T[r].rs=,T[l].ms=T[r].ms=T[x].sam;
T[x].sam=-INF,T[x].rev=;
}
if(T[x].rev){
T[x].rev=,T[l].rev^=,T[r].rev^=;
_swap(T[l].ch[],T[l].ch[]),_swap(T[r].ch[],T[r].ch[]);//MISTAKE:again:typo.
_swap(T[l].ls,T[l].rs),_swap(T[r].ls,T[r].rs);//!MISTAKE:when giving down'rev'tag,update children at once!
}
}
inline void Rotate(int x){
int y=T[x].f,z=T[y].f,d=dir(x);
T[y].ch[d]=T[x].ch[d^],T[T[x].ch[d^]].f=y;
T[z].ch[dir(y)]=x,T[x].f=z;
T[x].ch[d^]=y,T[y].f=x;pushup(y),pushup(x);
}
inline void Splay(int x,int to){
while(T[x].f^to){if(T[T[x].f].f^to) dir(T[x].f)^dir(x)?Rotate(x):Rotate(T[x].f);Rotate(x);}
if(!to)rt=x;
}
int Query_kth(int x,int k){
pushdown(x);
if(k<=T[T[x].ch[]].siz)return Query_kth(T[x].ch[],k);
else if(k==T[T[x].ch[]].siz+)return x;
return Query_kth(T[x].ch[],k-T[T[x].ch[]].siz-);
}
inline void Spilt(int l,int r){
l=Query_kth(rt,l),r=Query_kth(rt,r);
Splay(l,),Splay(r,l);//cerr<<"spilt:"<<endl;dbg(l),dbg(r);
}
void Build(int L,int R,int&x,int fa){
int mid=L+R>>;
x=id[mid],T[x].siz=,T[x].val=A[mid],T[x].f=fa;
T[x].sam=-INF,T[x].rev=;//MISTAKE:the lazy-tag which represents'MAKE_SAME' can't be zero at first.
if(L==R){
T[x].sum=T[x].val;T[x].ms=T[x].val;
T[x].val>?(T[x].ls=T[x].rs=T[x].val):(T[x].ls=T[x].rs=);
// dbg(x),dbg(T[x].sum),dbg(T[x].ls),dbg(T[x].rs),dbg(T[x].ms);
return;
}
if(L<mid)Build(L,mid-,T[x].ch[],x);if(mid<R)Build(mid+,R,T[x].ch[],x);pushup(x);
}
void prebuild(int L,int R,int&x,int fa){
int mid=L+R>>;x=id[mid],T[x].siz=,T[x].val=A[mid],T[x].f=fa,T[x].sam=-INF;
if(L==R){
T[x].sum=T[x].val;T[x].ms=T[x].val;if(x==||x==n+)T[x].ms=-INF;
T[x].val>?(T[x].ls=T[x].rs=T[x].val):(T[x].ls=T[x].rs=);
return;
}
if(L<mid)prebuild(L,mid-,T[x].ch[],x);if(mid<R)prebuild(mid+,R,T[x].ch[],x);pushup(x);
}
inline void Insert(int x,int cnt){
for(register int i=;i<=cnt;++i){
read(A[i]);
if(q.empty())id[i]=++tot;
else id[i]=q.front(),q.pop();
}
Spilt(x+,x+);Build(,cnt,T[T[rt].ch[]].ch[],T[rt].ch[]);
pushup(T[rt].ch[]),pushup(rt);//MISTAKE:DON'T FORGET PUSHUP!
}
inline void Erase(int&x){
if(!x)return;
Erase(T[x].ch[]),Erase(T[x].ch[]);
q.push(x);x=;
}
inline void Delete(int x,int cnt){
Spilt(x,x+cnt+);Erase(T[T[rt].ch[]].ch[]);
pushup(T[rt].ch[]),pushup(rt);
}
inline void make_same(int x,int cnt){
Spilt(x,x+cnt+);int y=T[T[rt].ch[]].ch[],c;read(c);
T[y].val=c,T[y].sam=c,T[y].sum=T[y].siz*c;
c>?(T[y].ls=T[y].rs=T[y].ms=T[y].sum):(T[y].ls=T[y].rs=,T[y].ms=c);//MISTAKE:'y',not 'x'!
pushup(T[rt].ch[]);pushup(rt);
}
inline void Reverse(int x,int cnt){
Spilt(x,x+cnt+);int y=T[T[rt].ch[]].ch[];
T[y].rev^=;_swap(T[y].ch[],T[y].ch[]),_swap(T[y].ls,T[y].rs);
}
inline void Query_sum(int x,int cnt){Spilt(x,x+cnt+);printf("%d\n",T[T[T[rt].ch[]].ch[]].sum);}
inline void Query_max_sum(){Spilt(,len+);printf("%d\n",T[T[T[rt].ch[]].ch[]].ms);}
char s[];int pos,cnt; int main(){//freopen("ttt.in","r",stdin);//freopen(".out","w",stdout);
len=read(n),read(m);
for(register int i=;i<=n;++i)read(A[i+]),id[i+]=i+;
id[]=,id[n+]=n+;tot=n+;T[].ms=-INF;//T[0].ms must be set zero!Think about the situation that a point has only one child when pushuping.
prebuild(,n+,rt,);
while(m--){
scanf("%s",s);
if(s[]=='I')read(pos),read(cnt),Insert(pos,cnt),len+=cnt;
else if(s[]=='D')read(pos),read(cnt),Delete(pos,cnt),len-=cnt;
else if(s[]=='K')read(pos),read(cnt),make_same(pos,cnt);
else if(s[]=='R')read(pos),read(cnt),Reverse(pos,cnt);
else if(s[]=='G')read(pos),read(cnt),Query_sum(pos,cnt);
else Query_max_sum();
}
return ;
}