今天做了两道Treap的模板题， 本来全是RE的，但仔细想想有没有可能O2优化的可能，结果一试，就全AC了

其中一题代码如下

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x7fffffff;
const int N = 1 << 18;
int n, tot, root, ans;
struct Treap {
	int l, r, val, dat, cnt;
} t[N];

int New(int val) {
	t[++tot] = (Treap) {
		0, 0, val, rand(), 1
	};
	return tot;
}

int build() {
	root = New(-INF), t[root].r = New(INF);
}

void zig(int &p) {
	int q = t[p].l;
	t[p].l = t[q].r;
	t[q].r = p;
	p = q;
}

void zag(int &p) {
	int q = t[p].r;
	t[p].r = t[q].l;
	t[q].l = p;
	p = q; 
}

void insert(int &p, int val) {
	if (p == 0) {
		p = New(val);
		return;
	} if (t[p].val == val) {
		t[p].cnt++;
		return;
	} if (val < t[p].val) {
		insert(t[p].l, val);
		if (t[t[p].l].dat > t[p].dat) zig(p);
	} else {
		insert(t[p].r, val);
		if (t[t[p].r].dat > t[p].dat) zag(p);
	}
}

int GetPre(int val) {
	int res = 1;
	int p = root;
	while (p > 0) {
		if (val == t[p].val) {
			res = p;
			break;
		}
		if (val > t[p].val) res = p, p = t[p].r;
		else p = t[p].l;
	}
	return t[res].val;
}

int GetNext(int val) {
	int res = 2;
	int p = root;
	while (p > 0) {
		if (val == t[p].val) {
			res = p;
			break;
		}
		if (val < t[p].val) res = p, p = t[p].l;
		else p = t[p].r;
	}
	return t[res].val;
}

int main() {
	build();
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int k;
		cin >> k;
		int minn = INF;
		int pre = GetPre(k);
		if (pre != -INF) minn = k - pre;  
		int next = GetNext(k);
		if (next != INF) minn = min(minn, next - k);
		if (i == 1) ans = k;
		else ans += minn;
		insert(root, k); 
	}
	cout << ans << endl;
	return 0;
}