HNOI2014 营业额统计

大致题意：给出n个数，每个数的最小波动值 = min{ | a[i]-a[j] | , 1<=j<i }，求n个数的最小波动值之和

题解：Splay 比较一下前驱、后继而已

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 101000

int root;
struct node
{
	int d,c,n,f,son[2];
}tr[maxn*2];int len;
int mymin(int x,int y){return (x<y)?x:y;}
void updata(int now)
{
	int lc=tr[now].son[0],rc=tr[now].son[1];
	tr[now].c=tr[lc].c+tr[rc].c+tr[now].n;
}
void add(int d,int f)
{
	len++;
	tr[len].d=d;tr[len].c=tr[len].n=1;
	tr[len].son[0]=tr[len].son[1]=0;
	tr[len].f=f;if (d<tr[f].d) tr[f].son[0]=len;else tr[f].son[1]=len;
}
void rotate(int x)
{
	int y=tr[x].f,z=tr[y].f,w,r,R;
	if (x==tr[y].son[0]) w=1;else w=0;
	
	r=tr[x].son[w];R=y;
	tr[R].son[1-w]=r;
	if (r!=0) tr[r].f=R;
	
	r=x;R=z;
	tr[R].son[ (tr[R].son[0]==y)?0:1 ]=r;
	tr[r].f=R;
	
	r=y;R=x;
	tr[R].son[w]=r;
	tr[r].f=R;
	
	updata(y);updata(x);
}
void splay(int x,int rt)
{
	while (tr[x].f!=rt)
	{
		int y=tr[x].f,z=tr[y].f;
		if (z==rt) rotate(x);
		else
		{
			if ((y==tr[z].son[0])==(x==tr[y].son[0])) rotate(y);
			else rotate(x);rotate(x);
		}
	}
	if (rt==0) root=x;
}
int findip(int d)
{
	int x=root;
	while (tr[x].d!=d)
	{
		if (d>tr[x].d)
		{
			if (tr[x].son[1]!=0) x=tr[x].son[1];
			else break;
		}else
		{
			if (tr[x].son[0]!=0) x=tr[x].son[0];
			else break;
		}
	}return x;
}
void ins(int d)
{
	if (root==0) {add(d,0);root=len;return;}
	int x=findip(d);
	if (tr[x].d==d) tr[x].n++;
	else add(d,x);
	updata(x);
	splay(x,0);
}
int rabs(int x){return (x<0)?-x:x;}
int main()
{
	//freopen("turnover.in","r",stdin);
	//freopen("turnover.out","w",stdout);
	int n,i,x;long long ans;
	scanf("%d",&n);
	scanf("%d",&x);
	ans=x;len=root=0;ins(x);
	for (i=2;i<=n;i++)
	{
		scanf("%d",&x);
		int y=findip(x),p=y,q=y;splay(y,0);
		if (x<tr[y].d && tr[y].son[0]!=0)
		{
			p=tr[y].son[0];
			while (tr[p].son[1]!=0) p=tr[p].son[1];
		}else if (x>tr[y].d && tr[y].son[1]!=0)
		{
			q=tr[q].son[1];
			while (tr[q].son[0]!=0) q=tr[q].son[0];
		}p=tr[p].d;q=tr[q].d;
		ans+=mymin(rabs(x-p),rabs(x-q));
		ins(x);
	}printf("%I64d
",ans);
	return 0;
}