https://www.luogu.org/problem/show?pid=2234
用Treap维护，每次查询这个数的前驱与后继哪个和它差值更小。
由于查询一个数时在Treap走出的路径必定经过它的前驱与后继，故直接在走的过程统计答案就可以了。
#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;
namespace treap
{
enum direction
{
l = ,
r =
};
struct node
{
int val, prio;
node *ch[];
node(int v) : val(v), prio(rand()) { ch[l] = ch[r] = NULL; }
int cmp(int v) { return (v < val) ? l : r; }
} * root;
void rotate(node *&t, int d)
{
node *k = t->ch[d ^ ];
t->ch[d ^ ] = k->ch[d];
k->ch[d] = t;
t = k;
}
void insert(int v, node *&t = root)
{
if (t == NULL)
t = new node(v);
else if (v == t->val)
return;
else
{
int d = t->cmp(v);
insert(v, t->ch[d]);
if (t->prio > t->ch[d]->prio)
rotate(t, d ^ );
}
}
int closest(int v, node *t = root) //返回与v的差的绝对值最小的差值
{
int ans = t == NULL ? v : abs(t->val - v);
while (t != NULL)
{
ans = min(ans, abs(t->val - v));
t = t->ch[t->cmp(v)];
}
return ans;
}
}
int main()
{
using namespace treap;
srand();
int n, tot = , a;
cin >> n;
while (n--)
{
cin >> a;
tot += closest(a);
insert(a);
}
cout << tot << endl;
return ;
}