给出一个数列，求∑i=1nminj=1i−1∣ai−aj∣\sum_{i=1}^{n}min_{j=1}^{i-1}|a_i-a_j|∑i=1nminj=1i−1∣ai−aj∣
输入样例 6512546 输出样例 12 样例解释5+∣1−5∣+∣2−1∣+∣5−5∣+∣4−5∣+∣6−5∣=5+4+1+0+1+1=125+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=125+∣1−5∣+∣2−1∣+∣5−5∣+∣4−5∣+∣6−5∣=5+4+1+0+1+1=12
数据范围1⩽n⩽32767,∣ai∣⩽1061\leqslant n \leqslant 32767,|a_i|\leqslant 10^61⩽n⩽32767,∣ai∣⩽106
解题思路用Splay存起来，然后每次找到最接近当前数的数（把当前数旋转为根节点，然后在左子树找最大，在右子树找最小）
代码 #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define ll long long#define N 40000using namespace std;int n, x, w, rt, ans, s[N], ls[N], rs[N], fa[N];int ss(int x){return x == ls[fa[x]];}void up(int x){int y = fa[x], z = fa[y], g = ss(x)? rs[x]: ls[x];if (z) ss(y)? ls[z] = x: rs[z] = x;if (ss(x)) rs[x] = y, ls[y] = g;else ls[x] = y, rs[y] = g;fa[x] = z;fa[y] = x;if (g) fa[g] = y;}void Splay(int x, int y)//旋转{while(fa[x] != y){if (fa[fa[x]] != y)ss(x) == ss(fa[x])? up(fa[x]): up(x);up(x);}if (!y) rt = x;}void add(int v)//加点{int x = rt, y = 0;while(x){y = x;if (v < s[x]) x = ls[x];else x = rs[x];}s[++w] = v;fa[w] = y;if (v < s[y]) ls[y] = w;else rs[y] = w;Splay(w, 0);}int ask()//查询{int x = ls[rt], y = rs[rt], xx, yy;//分别查询左右子树if (x) while(rs[x]) x = rs[x];//左子树最大的if (y) while(ls[y]) y = ls[y];xx = s[rt] - s[x];yy = s[y] - s[rt];if (!x) return yy;if (!y) return xx;return min(xx, yy);}int main(){scanf("%d", &n);scanf("%d", &ans);s[++w] = ans;rt = 1; while(--n){scanf("%d", &x);add(x);ans += ask();}printf("%d", ans);return 0;}
