题意：给出一组数，设定每个数与其前面的数之间最小相距值的绝对值为最小波动值（第一个数的最小波动值为其本身）。求所有最小波动值之和。
Splay入门题。此题仅包含插入，旋转和伸展操作。
可先参考Crash前辈的论文《运用伸展树解决数列维护问题》。
首先是旋转操作。
和一般的平衡树旋转操作类似，分为左旋和右旋。
将左儿子旋转至根，需要执行右旋操作。
旋转前：（x为左儿子，y为根节点） 旋转后：
将右儿子旋转至根节点，需要执行左旋操作。
旋转前：（y为右儿子，x为根节点） 旋转后：
显然，执行x旋操作，就是将!x儿子旋转至根节点，并把儿子的x子树替换给原根节点。
如果希望是根节点的儿子的儿子被旋转至根节点，则需要执行一字形操作或是之字形操作。
一字形：
例如右旋一字形，目的是将浅蓝色节点旋转至树根：首先将浅紫色节点旋转至根（右旋），然后将浅蓝色节点旋转至根（右旋）。
之字形：（仅显示一种，另一种对称）
（举例图上例子）
首先将绿色节点旋转至其父亲节点位置（右旋）；然后再旋转一次绿色节点（左旋）。
（两次都是旋转绿色节点）
接下来是伸展操作：
伸展操作与旋转操作联系十分紧密，伸展操作的目的，是将某节点x，通过一层层旋转，变成另外一个节点f的子节点。
假令x的父亲为y，y的父亲为z。
如果y的父亲已经是f，则只需一次单旋转；
如果不是则继续查询x，y和z之间的关系，以此来决定是一字形旋转，还是之字形旋转，然后将x挪至z；
继续前面的操作，直至x的父亲变为f。
接下来是插入操作和查询操作。
对于本题，每个数字都需要查询当前时刻，在数值上与其最相邻的数是什么。
此处则是巧妙运用Splay树性质的地方了：中序遍历一棵splay树，即是这个数组的顺序。
此题中，Splay树维护着一个按大小排序的数组。
显然最方便的操作是：插入一个数时，即将这个数旋转至根。这样查询遍十分方便。
深搜（左子节点小于父亲，右子节点大于父亲，不保存相同的值）当查询至某节点的值正好等于插入值时，仅需伸展一次（很大的可能性可以使得树更加平衡）；
当走至树的叶子节点也没有找到该插入值时，建立一个新点，插入该叶子节点的左子节点（值小于父亲节点）或右子节点（值大于父亲节点），并将插入的点旋转至树根处。
接下来按照中序遍历的性质即可，左相邻值是左子树的最右点，右相邻值是右子树的最左点。
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define MAXN 100010
#define INF 0x3f3f3f3f
struct SplayTree
{
int fa[MAXN], ch[MAXN][2], val[MAXN];
int cnt, root;
void New(int &t, int f, int v)
{
t = ++cnt;
fa[t] = f, val[t] = v;
ch[t][0] = ch[t][0] = 0;
}
//旋转操作，c = 0表示左旋，c = 1表示右旋
void Rotate(int x, int c)
{
int y = fa[x];
int z = fa[y];
ch[y][!c] = ch[x][c];
if(ch[x][c]) fa[ch[x][c]] = y;
fa[x] = fa[y];
if(fa[y])
{
if(ch[z][0] == y) ch[z][0] = x;
else ch[z][1] = x;
}
ch[x][c] = y, fa[y] = x;
if(y == root) root = x;
}
//Splay操作，表示把结点x转到结点f的下面
void Splay(int x, int f)
{
while(fa[x] != f)
{
int y = fa[x];
int z = fa[y];
//父节点即为f，执行单旋转
if(fa[y] == f)
{
if(ch[y][0] == x) Rotate(x, 1);
else Rotate(x, 0);
}
else
{
if(ch[z][0] == y)
{
if(ch[y][0] == x) Rotate(y, 1), Rotate(x, 1); //一字型旋转
else Rotate(x, 0), Rotate(x, 1); //之字形旋转
}
else
{
if(ch[y][1] == x) Rotate(y, 0), Rotate(x, 0); //一字形旋转
else Rotate(x, 1), Rotate(x, 0); //之字形旋转
}
}
}
if(f == 0) root = x;
}
int l()
{
int t = root;
if(ch[t][0] == 0) return INF;
t = ch[t][0];
while(ch[t][1]) t = ch[t][1];
return val[t];
}
int r()
{
int t = root;
if(ch[t][1] == 0) return INF;
t = ch[t][1];
while(ch[t][0]) t = ch[t][0];
return val[t];
}
int Insert(int k)
{
int r = root, c;
while(true)
{
if(val[r] == k)
{
Splay(r, 0);
return 0;
}
c = k < val[r] ? 0 : 1;
if(ch[r][c] == 0) break;
r = ch[r][c];
}
c = k < val[r] ? 0 : 1;
New(ch[r][c], r, k);
Splay(ch[r][c], 0);
return 1;
}
}splay;
int main()
{
int n;
while(~scanf("%d", &n))
{
int ans = 0;
splay.root = splay.cnt = 0;
for(int i = 0; i < n; i++)
{
int x = 0;
scanf("%d", &x);
if(!i)
{
ans += x;
splay.New(splay.root, 0, x);
}
else
{
int t = splay.Insert(x);
if(!t) continue;
int l = splay.l();
int r = splay.r();
ans += min(abs(l - x), abs(r - x));
}
}
printf("%d\n", ans);
}
return 0;
}