splay玄學，神奇，多變，應用廣。均攤時間複雜度O（n log n） (不會證明，好像都是這麼說“可以證明”的，單次最壞情況是O(n）,但是平均下來是n log n).
思路很簡單，基于rotate操作，和splay把某個點旋到那個節點之下。
幾乎所有的操作都需要splay.
花了好長時間研究怎麼寫更簡便，之後總結出了屬于自己的參考模闆。
（功能不全，基于bzoj1588的）
傳送門：http://www.lydsy.com/JudgeOnline/problem.php?id=1588
開始嘗試結構體數組版本，發現寫起來手殘啊，現改用指針版本，較為友善。
必備知識：splay的性質，左旋右旋，zigzag和zigzig.
splay也是一種平衡樹，是相當于科學的紅黑樹的替代品（紅黑樹碼量太長了），效率波動接近于treap(treap要快一點，是用堆維護的，但是應用有局限性（當然不是平衡樹一類）)
splay性質：穩定維護的樹的中序周遊不變，且中序周遊對應原數組排列。每個節點的左子樹的所有元素一定比這個節點元素小，右子樹所有元素比其大（不考慮重複元素）。
左旋右旋：左右旋不改變這棵樹的平衡性，将一個節點旋到它父節點的位置，且一般需要考慮3個節點（子，父，祖節點）.
zigzag和zigzig：我們發現3個節點在一條線上的時候，把最下面的連續旋兩次又會變成單鍊，這樣下次通路的時候就很慢，為了保證效率，我們需要使它的高度盡可能小，是以，在不斷的總結中我們發現，每次考慮連續兩次旋轉，可以降低整棵樹高度。
不清楚思路的個人建議參考：http://blog.csdn.net/leolin_/article/details/6436037
目前必須掌握的是rotate和splay.
基于bzoj還需要插入和尋找前驅和後繼。（根據樹的平衡型，前把某個點splay到根，前驅就是左子樹的最右節點，後繼就是右子樹的最左節點）。
初始化：
struct node
{
node *f;
node *ch[2];
int v;
node()
{
f=ch[0]=ch[1]=NULL;
v=0;
}
}S[maxn];
node *root;
S[]數組是為這棵樹靜态申請的位址空間，每次建立節點就放一個位置。
rotate(雙旋合一，了解的時候需要假設情況，假設左旋右旋)
void rotate(node *u)
{
node *f=u->f;
if(f==NULL)return ;
int d=u==f->ch[1];
node *ff=f->f;
int dd=0;
if(ff!=NULL)dd=f==ff->ch[1];//bug
f->ch[d]=u->ch[d^1];
if(u->ch[d^1]!=NULL)u->ch[d^1]->f=f;
u->ch[d^1]=f;
f->f=u;
u->f=ff;
if(ff!=NULL)ff->ch[dd]=u;
}
splay: 每次考慮連續兩次旋轉（除了最後一次），下面這個是考慮把u選到p下面
void splay(node *u,node *p)//把u旋轉到p的下面
{
while(u->f!=p)
{
node *f=u->f;
node *ff=f->f;
if(ff==p)
{
rotate(u);
break;
}
int d=u==f->ch[1];
int dd=f==ff->ch[1];
if(d==dd)rotate(f);
else rotate(u);
rotate(u);
}
if(p==NULL)root=u;
}
插入：當插入一個元素的時候，我們需要找到合适的位置（空樹特判），比目前節點小就看該節點的左兒子是否存在，存在繼續找，不存在建立新節點；右邊是一樣的道理。
（切記，插入之後把新節點旋到根，不要問我為什麼，這就是splay的玄學之處，不這樣做在一些題中很可能逾時）
void insert(int key)
{
if(root==NULL)//空樹
{
root=&S[++ncnt];
root->v=key;
return ;
}
node *x=root;
node *y;
while(1)
{
//分向左找和向右找
if(key<x->v)
{
if(x->ch[0])x=x->ch[0];
else//插入
{
y=&S[++ncnt];
y->v=key;
y->f=x;
x->ch[0]=y;
break;
}
}
else
{
if(x->ch[1])x=x->ch[1];
else
{
y=&S[++ncnt];
y->v=key;
y->f=x;
x->ch[1]=y;
break;
}
}
}
splay(y,NULL);
}
前後繼不多說了，相信不成問題。
如果放心不下，你可以周遊這棵樹檢查。
最後，附上AC代碼：
#include<cstdio>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#define maxn 100000+20
using namespace std;
int n;
int ncnt=0;
int ans=0;
struct node
{
node *f;
node *ch[2];
int v;
node()
{
f=ch[0]=ch[1]=NULL;
v=0;
}
}S[maxn];
node *root;
void rotate(node *u)
{
node *f=u->f;
if(f==NULL)return ;
int d=u==f->ch[1];
node *ff=f->f;
int dd=0;
if(ff!=NULL)dd=f==ff->ch[1];//bug
f->ch[d]=u->ch[d^1];
if(u->ch[d^1]!=NULL)u->ch[d^1]->f=f;
u->ch[d^1]=f;
f->f=u;
u->f=ff;
if(ff!=NULL)ff->ch[dd]=u;
}
void splay(node *u,node *p)//把u旋轉到p的下面
{
while(u->f!=p)
{
node *f=u->f;
node *ff=f->f;
if(ff==p)
{
rotate(u);
break;
}
int d=u==f->ch[1];
int dd=f==ff->ch[1];
if(d==dd)rotate(f);
else rotate(u);
rotate(u);
}
if(p==NULL)root=u;
}
//旋到根再通路
void insert(int key)
{
if(root==NULL)//空樹
{
root=&S[++ncnt];
root->v=key;
return ;
}
node *x=root;
node *y;
while(1)
{
//分向左找和向右找
if(key<x->v)
{
if(x->ch[0])x=x->ch[0];
else//插入
{
y=&S[++ncnt];
y->v=key;
y->f=x;
x->ch[0]=y;
break;
}
}
else
{
if(x->ch[1])x=x->ch[1];
else
{
y=&S[++ncnt];
y->v=key;
y->f=x;
x->ch[1]=y;
break;
}
}
}
splay(y,NULL);
}
int qian(node *u)//找u的前驅
{
node *x=u->ch[0];
if(x==NULL)return 0x3f3f3f3f;
while(x->ch[1]!=NULL)x=x->ch[1];
return x->v;
}
int hou(node *u)
{
node *x=u->ch[1];
if(x==NULL)return 0x3f3f3f3f;
while(x->ch[0]!=NULL)x=x->ch[0];
return x->v;
}
void dfs(node *u)
{
printf("%d ",u->v);
if(u->ch[0])dfs(u->ch[0]);
if(u->ch[1])dfs(u->ch[1]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
if(scanf("%d",&x)==EOF)x=0;
insert(x);//旋到根
int ll=qian(root);
int rr=hou(root);
if(ll==0x3f3f3f3f&&rr==0x3f3f3f3f)ans+=x;
else ans+=min(abs(ll-x),abs(rr-x));
//if(i==5)dfs(root);
}
printf("%d\n",ans);
return 0;
}
本人不才，蒟蒻一枚，希望早日熟練掌握splay.
![樹的基本概念(定義、基本術語、性質)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)