题目
简化题意
给你一个长为 (n) 的序列,让你求 (sumlimits_{i = 1} ^ {n} min (abs(a_j - a_i)),j in [1, i - 1))
思路
Splay。
对于一颗建好的 Splay 每次插入 (a_i),最小的贡献只有可能出现在前驱和后继中。
Code
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 33333
int min(int a, int b) { return a < b ? a : b; }
inline void read(int &T) {
int x = 0;
bool f = 0;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = !f;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
T = f ? -x : x;
}
int n, ans, root, fa[MAXN], son[MAXN][2];
int num, size[MAXN], val[MAXN], cnt[MAXN];
namespace Splay {
int which(int x) { return son[fa[x]][1] == x ? 1 : 0; }
void update(int x) { size[x] = cnt[x] + size[son[x][0]] + size[son[x][1]]; }
void clear(int x) { fa[x] = son[x][0] = son[x][1] = cnt[x] = size[x] = val[x] = 0; }
void rotate(int x) {
int father = fa[x], grandpa = fa[father];
int flag1 = which(x), flag2 = which(father);
fa[x] = grandpa, fa[father] = x;
if (grandpa) son[grandpa][flag2] = x;
fa[son[x][flag1 ^1]] = father;
son[father][flag1] = son[x][flag1 ^1];
son[x][flag1 ^ 1] = father;
update(x), update(father);
}
void splay(int x) {
for (int f = fa[x]; f = fa[x], f; rotate(x)) {
if (fa[f]) rotate(which(x) == which(f) ? f : x);
}
root = x;
}
int pre() {
int now = son[root][0];
while (son[now][1]) now = son[now][1];
return now;
}
int nxt() {
int now = son[root][1];
while (son[now][0]) now = son[now][0];
return now;
}
void ins(int x) {
if (!root) {
val[++num] = x;
++cnt[num];
root = num;
update(num);
return;
}
int now = root, f = 0;
while (1) {
if (val[now] == x) {
++cnt[now];
update(now), update(f);
splay(now);
return;
}
f = now, now = son[now][val[now] < x];
if (!now) {
val[++num] = x;
++cnt[num];
fa[num] = f;
son[f][val[f] < x] = num;
update(num), update(f);
splay(num);
return;
}
}
}
}
int main() {
read(n);
for (int i = 1, x; i <= n; ++i) {
read(x);
Splay::ins(x);
if (i == 1) ans += x;
else if (cnt[root] > 1) continue;
else {
int minn = 2147483647, maxx = 2147483647;
if (son[root][0]) minn = val[Splay::pre()];
if (son[root][1]) maxx = val[Splay::nxt()];
ans += min(abs(minn - x), abs(maxx - x));
}
}
std::cout << ans << '
';
return 0;
}