题意分析
给定 $a_1,a_2,a_3,\cdots,a_n$，对于每一个 $a_i$（$1<i\leq n$），在 $a_1,a_2,\cdots,a_{i-1}$ 中找一个 $a_j$，使得 $\sum\vert a_i-a_j\vert$ 最小。
即找 $a_i$ 的前驱与后继。
很容易想到平衡树维护。
$\text{Updated at 2025/7/20}$
此时迁移 Blog 的我非常懵 b，我理解不了一个普及−（虽然当时是普及/提高−）的题目我为什么要写 FHQ Treap。
况且 $n\leq32767$，你直接 $\mathcal O\left(n^2\log n\right)$ 排序写完不就好了吗？
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<random>
using namespace std;
#define int long long
const int N=1e5;
mt19937 Rand(time(0));
int root;
struct treap{
struct node{
int value,rand,size;
int left,right;
}t[N+1];
void up(int p){
t[p].size=t[t[p].left].size+t[t[p].right].size+1;
}
void split(int p,int x,int &l,int &r){
if(p==0)l=r=0;
else{
if(t[p].value<=x){
l=p;
split(t[p].right,x,t[p].right,r);
}else{
r=p;
split(t[p].left,x,l,t[p].left);
}up(p);
}
}
int merge(int l,int r){
if(!l||!r)return l|r;
if(t[l].rand<t[r].rand){
t[l].right=merge(t[l].right,r);
up(l);
return l;
}else{
t[r].left=merge(l,t[r].left);
up(r);
return r;
}
}
int create(int x){
static int top;
t[++top]={x,Rand(),1,0,0};
return top;
}
void insert(int x){
int l,r;
split(root,x,l,r);
root=merge(merge(l,create(x)),r);
}
void remove(int x){
int l,r,pl;
split(root,x,l,r);
split(l,x-1,l,pl);
pl=merge(t[pl].left,t[pl].right);
root=merge(merge(l,pl),r);
}
int rank(int x){
int l,r;
split(root,x-1,l,r);
int ans=t[l].size+1;
root=merge(l,r);
return ans;
}
int kth(int k,int p=root){
if(k<1||k>t[p].size)return 2147483647;
while(true){
if(t[t[p].left].size+1==k)break;
else if(k<t[t[p].left].size+1)p=t[p].left;
else{
k-=t[t[p].left].size+1;
p=t[p].right;
}
}return t[p].value;
}
int prev(int x){
int l,r;
split(root,x/*-1*/,l,r);
int ans=kth(t[l].size,l);
root=merge(l,r);
return ans;
}
int next(int x){
int l,r;
split(root,x,l,r);
int ans=kth(1,r);
root=merge(l,r);
return ans;
}
}t;
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
int n;
scanf("%lld",&n);
int ans;
scanf("%lld",&ans);
t.insert(ans);
for(int i=2;i<=n;i++){
int x;
scanf("%lld",&x);
ans+=min(abs(t.prev(x)-x),abs(t.next(x)-x));
t.insert(x);
}printf("%lld\n",ans);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
