本题题解并不详细，不推荐大家看这一篇。
可以看这篇
题目描述
请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）
100%的数据中，任何时刻数列中最多含有 500 000 个数。
100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。
100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 。
题解：
刷完普通平衡树，文艺平衡树板子后，本题纯靠自己想，用了3h打码，4h调试，共7h多终于AC了。
此题我认为堪称“平衡树观止”
题目就是这么地裸。但就是让你写不出来。
粗略地说一下splay题解：
要用到：
1.n+2个点，1，n+2是方便提取用的。
2.哨兵0号点，
3.每个点维护：fa,ch[2],sz,sum,val,lm,rm,ans最后三个是最大子段和用的。
和标记：chan,rev
4.用long long
知识点：
1.区间提取，l-1到根，r+1到根的右儿子。根右儿子的左子树就是操作区间。
2.区间打标记，直接打。
3.找区间左端点，右端点等，返回第k大位置节点编号。
显然不能直接把端点当做编号。因为根本不知道原始编号转到哪里去了。
4.pushdown时机：
pushdown本质是为了将序列保持真正的情况，所以一旦触及，必须pushdown，否则形态一变，子树一换，都完了。
每次查找kth的x，因为每次查找对应一次splay，必须一路上都pushdown，
并且影响的只有rt到x路径上的点，所以其他位置可以不用pushdown
子树内部也是不会动的，不用pushdown。
5.pushup时机：
本质是为了更新信息，所以一个节点变化了，或者其子树变化了，都要pushup
splay里面有，也是路径上改变的点都会pushup的。
另外，操作区间操作后，该子树可能有了变化，还要pushup（根右儿子），pushup（根），别的节点也不会被这次操作影响。
6.1号点和n+2号点。为了不影响答案（可能是负数），所以权值为-inf，并且这两个点一定要保证在区间的两端。
7.0号哨兵
因为我这里是钦定lm，rm，ans都必须选择一个。所以0号的rm，lm，ans都是-inf，才不会因为设成0而取不到负数答案。
8.卡空间（bzoj64MB）
而同一时刻最多500000个。必须垃圾回收，dp[N],dc
操作：
1.插入：直接插成一个链可以，但是之后复杂度并不优秀。
可以分治处理。每次插入mid递归l，mid-1和mid+1，r,数的高度就直接logn了。
开始的加入原数列也是。
对于新加入一些数，先像这样建成一棵树，然后类似区间提取pos，pos+1。
那么，pos+1左儿子就是新树根的fa了，直接嫁接上去。记得pushup（pos+1）与（pos）
见ins，pre函数
2.删除。区间提取、然后直接删除rt的右儿子的左儿子。
要先进入这个子树，放进回收池里。
3.修改。区间提取，直接改。
4.翻转。区间提取。翻转标记。
注意，必须打标记的同时，就要翻转儿子，交换lm，rm
因为虽然是懒标记，但是对于这个节点的影响必须处理。
否则splay时可能会出锅。
因为x左右儿子会有标记，但不翻转，然后rotate(x)会交换子树，pushup(y)就把没有真正正确的x曾经的子树信息记录上去了。
5.区间和。区间提取。直接返回sum
6.最大子段和。直接返回t[rt].ans
注意事项：
1.保护哨兵，保护哨兵，保护哨兵。
2.任何时候，在splay(x)之前，必须确定x路径上的所有点都pushdown了。
3.pushup中，t[x].ans情况较多，不要忘了可以是t[x].val
4.swap(lm,rm)别错了。
代码：
#include<bits/stdc++.h>
#define rs t[x].ch[1]
#define ls t[x].ch[0]
#define numb ch-'0'
#define ri register int
#define il inline
using namespace std;
typedef long long ll;
const int N=+;
const ll inf=(1LL*<<);
char ch;
il void rdint(int &x){
x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
il void rdll(ll &x){
x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
struct node{
int ch[],fa;
ll rm,lm,sum,ans;
int rev;
ll chan;
ll val;
int sz;
void init(int f,ll v){
fa=f,val=v;rm=v;lm=v,ans=v,sum=v;
rev=,chan=inf;
sz=;
}
}t[N];
il ll Max(ll a,ll b){
return a>b?a:b;
}
int dc,dp[N],pc;
int n,m,rt;
ll st[N];
il int nc(){
int r=dc?dp[dc--]:++pc;
memset(t+r,,sizeof (node));return r;
}
il void pushup(int x){
t[x].sum=t[t[x].ch[]].sum+t[t[x].ch[]].sum+t[x].val;
t[x].rm=Max(t[t[x].ch[]].rm,Max(t[t[x].ch[]].sum+t[x].val,t[t[x].ch[]].sum+t[x].val+t[t[x].ch[]].rm));
t[x].lm=Max(t[t[x].ch[]].lm,Max(t[t[x].ch[]].sum+t[x].val,t[t[x].ch[]].sum+t[x].val+t[t[x].ch[]].lm));
t[x].ans=Max(t[x].lm,t[x].rm);
t[x].ans=Max(t[x].ans,Max(t[t[x].ch[]].rm+t[x].val+t[t[x].ch[]].lm,Max(t[t[x].ch[]].rm+t[x].val,t[x].val+t[t[x].ch[]].lm)));
t[x].ans=Max(t[x].ans,Max(t[t[x].ch[]].ans,t[t[x].ch[]].ans));
t[x].ans=Max(t[x].ans,t[x].val);//bug 2
t[x].sz=t[t[x].ch[]].sz+t[t[x].ch[]].sz+;
}
il void pushdown(int x){
if(t[x].chan!=inf){
if(ls){
t[ls].chan=t[x].chan;
t[ls].val=t[x].chan;
t[ls].sum=t[ls].val*t[ls].sz;
t[ls].rm=t[ls].lm=t[ls].ans=t[ls].val>?t[ls].sum:t[ls].val;
}
if(rs){
t[rs].chan=t[x].chan;
t[rs].val=t[x].chan;
t[rs].sum=t[rs].val*t[rs].sz;
t[rs].rm=t[rs].lm=t[rs].ans=t[rs].val>?t[rs].sum:t[rs].val;
}
t[x].chan=inf;
}
if(t[x].rev){
if(ls&&t[ls].val!=-inf){
t[ls].rev^=;
swap(t[ls].lm,t[ls].rm);//bug1
}
if(rs&&t[rs].val!=-inf){
t[rs].rev^=;
swap(t[rs].lm,t[rs].rm);//bug1
}
swap(ls,rs);
t[x].rev=;
}
}
il void rotate(int x){
int y=t[x].fa,d=t[y].ch[]==x;
t[t[y].ch[d]=t[x].ch[!d]].fa=y;
t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[]==y]=x;
t[t[x].ch[!d]=y].fa=x;
pushup(y);
}
il void splay1(int x,int f){
while(t[x].fa!=f){
int y=t[x].fa,z=t[y].fa;
if(z!=f){
rotate((t[y].ch[]==x)==(t[z].ch[]==y)?y:x);
}
rotate(x);
}
pushup(x);
if(f==) rt=x;
}
il int kth(int k){
int x=rt;
while(){
pushdown(x);
int d=k-t[t[x].ch[]].sz;
if(d<=) x=t[x].ch[];
else if(d==) return x;
else{
k=d-;
x=t[x].ch[];
}
}
}
int newrt;
il void splay2(int x,int f){
while(t[x].fa!=f){
int y=t[x].fa,z=t[y].fa;
if(z!=f){
rotate((t[y].ch[]==x)==(t[z].ch[]==y)?y:x);
}
rotate(x);
}
pushup(x);
if(f==) newrt=x;
}
il void build(ll v){
if(!newrt){
newrt=nc();
t[newrt].init(,v);
return;
}
int x=newrt;
while(){
if(!t[x].ch[]){
t[x].ch[]=nc();
t[t[x].ch[]].init(x,v);
x=t[x].ch[];
break;
}
x=t[x].ch[];
}
splay2(x,);
}
il int pre(int l,int r,int f){
if(l>r){
return ;
}
int mid=(l+r)>>;
int x=nc();
t[x].init(f,st[mid]);
t[x].ch[]=pre(l,mid-,x);
t[x].ch[]=pre(mid+,r,x);
pushup(x);
return x;
}
il void ins(int pos,int tot){
newrt=;
for(ri i=;i<=tot;i++){
rdll(st[i]);
}
newrt=pre(,tot,);
int x=kth(pos+);
int y=kth(pos+);
splay1(x,);
splay1(y,x);
t[y].ch[]=newrt;
t[newrt].fa=y;
pushup(y);
pushup(x);
}
il void del(int x){
if(t[x].ch[]) del(t[x].ch[]);
dp[++dc]=x;
if(t[x].ch[]) del(t[x].ch[]);
}
il void remove(int pos,int tot){
int l=kth(pos);
int r=kth(pos+tot+);
splay1(l,);
splay1(r,l);
del(t[r].ch[]);
t[r].ch[]=;
pushup(r);
pushup(l);
}
il void upda(int pos,int tot,ll c){
int l=kth(pos);
int r=kth(pos+tot+);
splay1(l,);
splay1(r,l); int x=t[r].ch[];
t[x].chan=c;
t[x].val=c;
t[x].sum=t[x].val*t[x].sz;
t[x].rm=t[x].lm=t[x].ans=t[x].val>?t[x].sum:t[x].val; pushup(r);
pushup(l);
}
il void reverse(int pos,int tot){
int l=kth(pos);
int r=kth(pos+tot+);
splay1(l,);
splay1(r,l); int x=t[r].ch[];
t[x].rev^=;
swap(t[x].lm,t[x].rm); pushup(r);
pushup(l);
}
il ll qs(int pos,int tot){
int l=kth(pos);
int r=kth(pos+tot+);
splay1(l,);
splay1(r,l); int x=t[r].ch[];
int ret=t[x].sum;
pushdown(x);//bug 3
splay1(x,);
return ret;
} int main()
{
t[].lm=t[].rm=t[].ans=-inf;//warning warning warning !!!
t[].sz=;t[].sum=;
scanf("%d%d",&n,&m);
st[]=-inf;
for(int i=;i<=n+;i++){
rdll(st[i]);
}
st[n+]=-inf; rt=pre(,n+,);
char lp[];
int pos,tot;
ll c;
int cnt=;
for(ri i=;i<=m;i++){
ch=getchar();
while(ch>'Z'||ch<'A')ch=getchar();
for(cnt=;(ch=='-')||(ch<='Z'&&ch>='A');ch=getchar())lp[++cnt]=ch;
if(lp[]=='I'){
rdint(pos),rdint(tot);
if(tot==) continue;
ins(pos,tot);
}
else if(lp[]=='D'){
rdint(pos),rdint(tot);
if(tot==) continue;
remove(pos,tot);
}
else if(lp[]=='M'&&lp[]=='K'){
rdint(pos),rdint(tot);rdll(c);
if(tot==) continue;
upda(pos,tot,c);
}
else if(lp[]=='M'&&lp[]=='X'){
printf("%lld\n",t[rt].ans);
}
else if(lp[]=='G'){
rdint(pos),rdint(tot);
if(tot==) printf("0\n");
else printf("%lld\n",qs(pos,tot));
}
else if(lp[]=='R'){
rdint(pos),rdint(tot);
if(tot==) continue;
reverse(pos,tot);
}
}
return ;
}
总结：
数据结构，就是利用一种结构，维护数的算法。通常为了减少时间复杂度，而牺牲一些空间作为代价。
就是在保证查询、修改正确的情况下，最大限度地减少时间复杂度。
为了保证复杂度，每个数据结构都有自己的方式。
splay平衡树结构的灵魂函数：splay，rotate
维护正确性并且节省时间的灵魂函数：pushdown，pushup
这四个函数写对，整个平衡数的框架就建立起来了。
将二者有机结合起来，就能够达到时间和正确性的统一。
数据结构基本都是这样。