Ryan_<

我的第一棵Splay Tree,多种数据结构可解。当做模板了。

其中主要操作是找到前驱和后继，作为一棵二叉查找树，这并不困难。一个节点的后继，便是右子树中的最左的结点，前驱便是左子树中最右边的节点。

#include<cstdio>
#include<iostream>
#define inf 0x7fffffff
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,s,t) for(int i=(s);i<=(t);i++)
using namespace std;
const int N=50000;//32767
int n,tot,rt,t1,t2,ans;
int num[N];//每个节点的值
int tr[N][2];//splay tree 每个节点左右结点的编号
int fa[N];//父节点编号

/*Splay操作时从上往下的，p==0表示根节点*/

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
	return x*f;
}

/*rotate 旋转操作
根据l,r进行左旋/右旋
*/
void rotate(int x,int &p)
{
	int y=fa[x],z=fa[y],l,r;
	if(tr[y][0]==x) l=0;
	else l=1;
	r=l^1;
	if(y==p)
		p=x;//修改根节点
	else//z==p
		{
			if(tr[z][0]==y) tr[z][0]=x;
			else tr[z][1]=x;
		}
	fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;
	tr[y][l]=tr[x][r];tr[x][r]=y;
}

/*Splay 伸展操作——splay的核心操作
将编号为x的节点旋至根部
*/
void splay(int x,int &p)
{
	int y,z;
	while(x!=p)
	{
		y=fa[x],z=fa[y];
		if(y!=p)
		{
			if((tr[y][0]==x)^(tr[z][0]==y))//情况3
				rotate(x,p);
			else//情况2
				rotate(y,p);
		}
		rotate(x,p);//情况1
	}
}


/*
Insert：将元素x插入伸展树S表示的有序集中。
首先也与处理普通的二叉查找树一样，将x插入到伸展树S中的相应位置上，
再执行Splay(x,S)。

注意，这里将根节点父节点赋值为0，不会与叶节点冲突——
显然不会有节点的父节点为叶节点
又因为Splay操作是由上到下的，也保证改写法正确性
*/
void ins(int &p,int x,int last)
{
	if(!p)
	{
		tot++;p=tot;
		num[p]=x;fa[p]=last;
		splay(p,rt);
		return;
	}
	if(x<num[p])
		ins(tr[p][0],x,p);
	else
		ins(tr[p][1],x,p);
}


/*ask_before:求前驱
是不是有点像upper_bound的操作？
*/
void ask_before(int p,int x)
{
	if(!p) return;
	if(num[p]<=x)
	{
		t1=num[p];
		ask_before(tr[p][1],x);
	}
	else ask_before(tr[p][0],x);
}

/*ask_after:求后继
同样，与lower_bound操作近似
*/
void ask_after(int p,int x)
{
	if(!p) return;
	if(num[p]>=x)
	{
		t2=num[p];
		ask_after(tr[p][0],x);
	}
	else ask_after(tr[p][1],x);
}

int main()
{
	n=read();
	for1(i,n)
	{
		int x;
		if(scanf("%d",&x)==EOF) x=0;
		t1=-inf;t2=inf;
		ask_before(rt,x);
		ask_after(rt,x);
		if(i==1) ans+=x;
		else ans+=min(x-t1,t2-x);
		ins(rt,x,0);
	}
	printf("%d\n",ans);
	return 0;
}