RT,求助大佬

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

inline char nc () {static char buf[1 << 21], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;}

inline int read () { 
    register int x(0),f(1); char ch = getchar(); 
    while (ch > '9' || ch < '0') {if (ch == '-') f = ~f +1; ch = getchar();} 
    while (ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();} 
    return x * f;
}

const int maxn = 1e5+5;
int n;
const double alpha = 0.75;

struct node {
	int l, r, val;
	int size, fact;
	bool exist;
}tzy[maxn];

int val[maxn];
int root, cnt, qwq, wqw;
long long ans;

void newnode (int &now, int val) {
	now = ++cnt;
	tzy[now].val = val;
	tzy[now].r = tzy[now].l = 0;
	tzy[now].fact = tzy[now].size = 1;
	tzy[now].exist = 1;
}

bool imbalence (int now) {
	if (std::max(tzy[tzy[now].l].size, tzy[tzy[now].r].size) > tzy[now].size * alpha
		|| tzy[now].size - tzy[now].fact > tzy[now].size * 0.3)
		return true;
	return false;
}

#include <vector>
std::vector<int>v;

void ldr (int now) {
	if (!now) return ;
	ldr (tzy[now].l);
	if (tzy[now].exist) v.push_back(now);
	ldr (tzy[now].r);
}

void lift (int l, int r, int &now) {
	if (l == r) {
		now = v[l];
		tzy[now].l = tzy[now].r = 0;
		tzy[now].size = tzy[now].fact = 1;
		tzy[now].exist = 1;
        return ;
	}
	int m = l + r >> 1;
	while (l < m && tzy[v[m]].val == tzy[v[m-1]].val) m--;
	now = v[m];
	if (l < m) lift (l, m-1, tzy[now].l);
	else tzy[now].l = 0;
	lift (m+1, r, tzy[now].r);
	tzy[now].size = tzy[tzy[now].l].size + tzy[tzy[now].r].size + 1;
	tzy[now].fact = tzy[tzy[now].l].fact + tzy[tzy[now].r].fact + 1;
}

void rebuild (int &now) {
	v.clear ();
	ldr (now);
	if (v.empty()) {
		now = 0;
		return ;
	}
	lift (0, v.size()-1, now);
	return ;
}

void update (int now, int end) {
	if (now == end) return ;
	if (tzy[end].val < tzy[now].val) update (tzy[now].l, end);
	else update (tzy[now].r, end);
	tzy[now].size = tzy[tzy[now].l].size + tzy[tzy[now].r].size + 1;
}

void check (int &now, int end) {
	if (now == end) return ;
	if (imbalence (now)) {
		rebuild (now);
		update (root, now);
		return ;
	}
	if (tzy[end].val < tzy[now].val) check (tzy[now].l, end);
	else check (tzy[now].r, end);
	return ;
}

void ins (int &now, int val) {
	if (!now) {
		newnode (now, val);
		check (root, now);
		return ;
	}
	tzy[now].size++;
	tzy[now].fact++;
	if (val < tzy[now].val) ins (tzy[now].l, val);
	else ins (tzy[now].r, val);

}

void del (int now, int val) {
	if (tzy[now].exist && tzy[now].val == val) {
		tzy[now].exist = 0;
		tzy[now].fact--;
		check (root, now);
		return ;
	}
	tzy[now].fact--;
	if (val < tzy[now].val) del (tzy[now].l, val);
	else del (tzy[now].r, val);
}

int getrank (int num) {
	int now = root, rank = 1;
	while (now) {
		if (num <= tzy[now].val) {
			now = tzy[now].l;
		}
		else {
			rank += tzy[tzy[now].l].fact + tzy[now].exist;
			now = tzy[now].r;
		}
	}
	return rank;
}

int getnum (int rank) {
	int now = root;
	while (now) {
		if (tzy[now].exist && tzy[now].exist + tzy[tzy[now].l].fact == rank) {
			break;
		}
		else if (tzy[tzy[now].l].fact >= rank) {
			now = tzy[now].l;
		}
		else {
			rank -= tzy[tzy[now].l].fact + tzy[now].exist;
			now = tzy[now].r;
		}
	}
	return tzy[now].val;
}
int main () {
	n = read ();
	for (register int i(1); i <= n; ++i) val[i] = read ();
	ins (root, val[1]);
	ans = val[1];
	for (register int i(2); i <= n; ++i) {	
		qwq = getnum (getrank (val[i])-1);	
		wqw = getnum (getrank (val[i]+1));
		ans += std::min (std::abs (val[i] - qwq), std::abs (val[i] - wqw));
		ins (root, val[i]);
	}
	printf("%lld\n", ans);
}