平衡树常规题，给出两种实现算法
Treap版：
//OJ 1610
//by Cydiater
//2016.9.1
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <ctime>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
;
const int oo=0x3f3f3f3f;
inline int read(){
,f=;
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
,tol=,maxx,minn,delta;
ll ans;
struct node{
int leftt,rightt,rnd,v;
}t[MAXN];
namespace solution{
void lefturn(int &k){
int tt=t[k].rightt;t[k].rightt=t[tt].leftt;t[tt].leftt=k;k=tt;
}
void righturn(int &k){
int tt=t[k].leftt;t[k].leftt=t[tt].rightt;t[tt].rightt=k;k=tt;
}
void insert(int &k,int x){
){
k=++tol;
t[k].leftt=t[k].rightt=;
t[k].v=x;t[k].rnd=rand();
return;
}
if(x==t[k].v)return;
else if(x>t[k].v){
insert(t[k].rightt,x);
if(t[t[k].rightt].rnd<t[k].rnd)lefturn(k);
}
else if(x<t[k].v){
insert(t[k].leftt,x);
if(t[t[k].leftt].rnd<t[k].rnd)righturn(k);
}
}
void query_delta(int k,int x){
) return;
if(x<=t[k].v)maxx=min(maxx,t[k].v);
if(x>=t[k].v)minn=max(minn,t[k].v);
if(x>t[k].v)query_delta(t[k].rightt,x);
else query_delta(t[k].leftt,x);
}
void slove(){
N=read();
up(i,,N){
num=read();
maxx=oo;minn=-oo;delta=oo;
query_delta(root,num);
if(maxx!=-oo)delta=min(delta,abs(maxx-num));
if(minn!=oo)delta=min(delta,abs(num-minn));
)delta=num;
ans+=delta;
//cout<<num<<' '<<delta<<' '<<ans<<endl;
insert(root,num);
}
}
void output(){
cout<<ans<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);
using namespace solution;
slove();
output();
;
}
Splay版：
//bzoj 1588
//by Cydiater
//2016.9.6
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
;
const int oo=0x3f3f3f3f;
inline int read(){
,f=;
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
map<int,int>lable;
struct SplayTree{
],v,siz,cnt,fa;
}t[MAXN];
,tol=,anss=;
namespace solution{
]==x;}
]=t[x].son[]=t[x].siz=t[x].cnt=t[x].fa=t[x].v=;}
void updata(int x){
if(x){
t[x].siz=t[x].cnt;
])t[x].siz+=t[t[x].son[]].siz;
])t[x].siz+=t[t[x].son[]].siz;
}
}
inline void rotate(int x){//rotate now node to root
int old=t[x].fa,oldf=t[old].fa,which=get(x);
t[old].son[which]=t[x].son[which^];t[t[old].son[which]].fa=old;
t[old].fa=x;t[x].son[which^]=old;
t[x].fa=oldf;
]==old]=x;
updata(old);updata(x);
}
void splay(int x){
for(int fa;(fa=t[x].fa);rotate(x))if(t[fa].fa)
rotate(get(x)==get(fa)?fa:x);root=x;
}
inline void insert(int v){
){
root=++tol;
t[root].son[]=t[root].son[]=t[root].fa=;
t[root].v=v;t[root].cnt=t[root].siz=;
return;
}
;
){
if(t[now].v==v){
t[now].cnt++;updata(now);updata(fa);
splay(now);break;
}
fa=now;now=t[now].son[t[now].v<v];
){
now=++tol;
t[now].son[]=t[now].son[]=;t[now].v=v;
t[now].siz=t[now].cnt=;t[now].fa=fa;
t[fa].son[t[fa].v<v]=tol;
updata(fa);
splay(now);
break;
}
}
}
int find(int x){
;
){
];
else{
ans+=(t[now].son[]?t[t[now].son[]].siz:);
if(t[now].v==x){
splay(now);
;
}
ans+=t[now].cnt;
now=t[now].son[];
}
}
}
int pre(){
];
])now=t[now].son[];
return now;
}
int nxt(){
];
])now=t[now].son[];
return now;
}
void del(int x){
int whatever=find(x);
){
t[root].cnt--;
t[root].siz--;
}
]+t[root].son[]==){
clear(root);root=;
return;
}
]){
];t[root].fa=;
clear(oldroot);return;
}]){
];t[root].fa=;
clear(oldroot);return;
}
int leftbig=pre(),oldroot=root;splay(leftbig);
t[t[oldroot].son[]].fa=root;t[root].son[]=t[oldroot].son[];
clear(root);updata(root);
}
void debug(int now){
printf(],t[now].son[],t[now].siz,t[now].cnt,t[now].fa,t[now].v);
])debug(t[now].son[]);
])debug(t[now].son[]);
}
}
int main(){
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);
using namespace solution;
N=read();
while(N--){
int num=read();if(lable[num])continue;
insert(num);lable[num]=;
int maxx=nxt(),minn=pre();
int tmp=oo;
)tmp=num;
if(maxx)tmp=min(tmp,t[maxx].v-num);
if(minn)tmp=min(tmp,num-t[minn].v);
anss+=tmp;
//debug(root);puts("");
}
printf("%d\n",anss);
;
}