P2234 Treap 零分求调

#include<bits/stdc++.h>
#define endl '\n'
#define  ls t[x].ch[0]
#define  rs t[x].ch[1]
using namespace std;
int n, a[1000000], sum;
long long ans, ans2;
int N = 100001, cnt;
struct treap {
	int ch[2], cnt, size, val, rd;
} t[100001];

void up(int x) {
	t[x].size = t[t[x].ch[0]].size + t[t[x].ch[1]].size + t[x].cnt;
}
void rotate(int &x, int d) { 
	int tem = t[x].ch[d];
	t[x].ch[d] = t[tem].ch[d^1];
	t[tem].ch[d ^ 1] = x;
	up(x);
	up(tem);
	x = tem;
}
void insert(int &x, int val) {
	if(!x) {               
		x = ++cnt;
		t[x].cnt = t[x].size = 1;
		t[x].val = val, t[x].rd = rand();
		return;
	}
	t[x].size++;          
	if(t[x].val == val) {
		t[x].cnt++;    
		return;
	}
	int d = t[x].val < val;
	insert(t[x].ch[d], val);               
	if(t[x].rd > t[t[x].ch[d]].rd) {
		rotate(x,d);
	}
}
void delet(int &x, int val) {
	if(!x) {
		return;
	}                                          
	if(t[x].val == val) {
		if(t[x].cnt > 1) {
			t[x].cnt--;
			t[x].size--;
			return;
		}                       
		bool d = t[ls].rd > t[rs].rd;
		if(ls == 0 || rs == 0) {
			x = ls + rs;
		} else {
			rotate(x, d);
			delet(x, val);
		} 
	} else {
		t[x].size--;
		delet(t[x].ch[t[x].val<val], val); 
	}
}
int kth(int root, int k) {
	int x = root;
	while(1) {
		if(k <= t[ls].size) {
			x = ls;
		} else if(k > t[ls].size + t[x].cnt) {
			k -= t[ls].size + t[x].cnt;
			x = rs;
		} else {
			return t[x].val;
		}
	}
}

int rnk(int x, int val) {
	if(!x) {
		return 0;
	}
	if(t[x].val == val) {
		return t[ls].size + 1;
	}
	if(t[x].val > val) {
		return rnk(ls, val);
	}
	return rnk(rs, val) + t[ls].size + t[x].cnt;
}
int pre(int x, int val) {
	if(!x) {
		return ans;
	}
	if(t[x].val < val) {
		ans = t[x].val;
		return pre(rs, val);
	}
	return pre(ls, val);
}

int nex(int x, int val) { 
	if(!x) {
		return ans;
	}
	if(t[x].val > val)  {
		ans = t[x].val;
		return nex(ls, val);
	}
	return nex(rs, val);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	cin >> a[1];
	int root = 0;
	insert(root,a[1]);
	root = 1;
	ans2 = a[1];
	for(int i = 2; i <= n; i++){
		cin >> a[i];
		ans2 += min(abs(pre(root,a[i]) - a[i]) , abs(nex(root,a[i]) - a[i])); 
//		cout << ans2 << " " << pre(root,a[i]) << endl;
		insert(root,a[i]);
	}
	cout << ans2;
	return 0;
}

链接