学习splay tree的模版题。
网址：http://www.wikioi.com/problem/1296/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 110000
#define INF 99999999
struct splaytree//封装伸展树
{//maxn:伸展树的点的个数int pre[maxn];//前驱int key[maxn];//键值int ch[maxn][2];//左右孩子int root,tot;//根节点，节点数量void init(){tot=root=0;memset(ch,0,sizeof(ch));memset(pre,0,sizeof(pre));memset(key,0,sizeof(key));}void newnode(int &r,int father,int k){//在r位置，父亲为father，新建一个值为x的新节点。r=++tot;pre[r]=father;key[r]=k;ch[r][0]=ch[r][1]=0;}void rot(int x,int kind){//kind=1,右旋.kind=0，左旋int y=pre[x];ch[y][!kind]=ch[x][kind];pre[ch[x][kind]]=y;ch[x][kind]=y;if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;pre[x]=pre[y];pre[y]=x;}void splay(int x,int goal){//把x伸展到目标位置while(pre[x]!=goal){if(pre[pre[x]]==goal)rot(x,ch[pre[x]][0]==x);else{int y=pre[x];int kind=ch[pre[y]][0]==y;if(ch[y][kind]==x){rot(x,!kind);rot(x,kind);}else{rot(y,kind);rot(x,kind);}}}if(goal==0)root=x;//把root更新成x}int insert(int x){//插入值xint r=root;while(ch[r][key[r]<x]){if(key[r]==x){splay(r,0);return 0;}r=ch[r][key[r]<x];}newnode(ch[r][x>key[r]],r,x);splay(ch[r][x>key[r]],0);return 1;}int get_pre(int x){//寻找节点x的前驱的值,未找到，反回INFint r=ch[x][0];if(r==0)return -INF;while(ch[r][1])r=ch[r][1];return key[r];}int get_next(int x){//寻找节点x的后继的值,未找到，反回INFint r=ch[x][1];if(r==0)return INF;while(ch[r][0])r=ch[r][0];return key[r];}
}tree;
int main()
{int n,i;while(~scanf("%d",&n)){int sum=0;int x;tree.init();for(i=1;i<=n;i++){if(scanf("%d",&x)==EOF)x=0;if(i==1){sum+=x;tree.newnode(tree.root,0,x);continue;}if(tree.insert(x)==0)continue;int a=tree.get_pre(tree.root);int b=tree.get_next(tree.root);// cout<<a<<" "<<x<<" "<<b<<endl;sum+=min(x-a,b-x);}printf("%d\n",sum);}return 0;
}