刚学平衡树，分别用了Splay和fhq-treap交了一遍。
这是Splay的板子，貌似比较短？
Splay
``` cpp
#include
#include
#include
#include
using namespace std;
const int N = 100005, INF = 2e9;
int n;
int nid, root;
int fa[N], ch[N][2];
int val[N];
int sz[N], rep[N];
void update(int x) {
sz[x] = sz[ch[x][0]]+sz[ch[x][1]]+rep[x];
}
void rotate(int x) {
int y = fa[x], z = fa[y];
int d = ch[fa[x]][1]x;
ch[z][ch[fa[y]][1]y] = x; fa[x] = z;
ch[y][d] = ch[x][d^1]; fa[ch[x][d^1]] = y;
ch[x][d^1] = y; fa[y] = x;
update(y); update(x);
}
void splay(int x, int goal) {
for(; fa[x] != goal; rotate(x)) if(fa[fa[x]] != goal)
(ch[fa[x]][0]x)^(ch[fa[fa[x]]][0]fa[x]) ? rotate(x) : rotate(fa[x]);
if(!goal) root = x;
}
void find(int v) {
int u = root;
if(!u) return ;
while(ch[u][val[u]<v] && val[u] != v) u = ch[u][val[u]<v];
splay(u, 0);
}
int findPre(int v) {
find(v);
int u = root;
if(val[u] < v) return u;
u = ch[u][0];
while(ch[u][1]) u = ch[u][1];
return u;
}
int findNxt(int v) {
find(v);
int u = root;
if(val[u] > v) return u;
u = ch[u][1];
while(ch[u][0]) u = ch[u][0];
return u;
}
void insert(int v) {
int u = root, f = 0;
while(u && val[u] != v) f = u, u = ch[u][val[u]<v];
if(u) rep[u]++;
else {
nid++;
fa[nid] = f;
ch[f][val[f]<v] = nid;
val[nid] = v;
sz[nid] = rep[nid] = 1;
u = nid;
}
splay(u, 0);
}
void del(int v) {
int pre = findPre(v), nxt = findNxt(v);
splay(pre, 0); splay(nxt, pre);
int tar = ch[nxt][0];
if(rep[tar] > 1) {
rep[tar]--;
splay(tar, 0);
}
else ch[nxt][0] = 0;
}
int kth(int x) {
if(sz[root] < x) return 0;
int u = root;
while(1) {
int lson = ch[u][0];
if(x <= sz[lson]) u = lson;
else if(x > sz[lson]+rep[u]) x -= sz[lson]+rep[u], u = ch[u][1];
else return val[u];
}
}
int main() {
insert(-(1<<31)+2); //添加两个哨兵节点，防止越界
insert((1<<31)-2);
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1, c, x; i <= n; i++) {
cin >> c >> x;
if(c == 1) insert(x);
else if(c == 2) del(x);
else if(c == 3) find(x), cout << sz[ch[root][0]] << endl;
else if(c == 4) cout << kth(x+1) << endl;
else if(c == 5) cout << val[findPre(x)] << endl;
else if(c == 6) cout << val[findNxt(x)] << endl;
}
return 0;
}
这是fhq-treap的板子（为了美观，我已经不能再无脑压行了）
<h3>fhq-treap</h3>
``` cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <ctime>
using namespace std;
const int N = 100005;
int n;
int ch[N][2], val[N], sz[N], rnd[N];
int nid, root;
void update(int x) {
sz[x] = sz[ch[x][0]]+sz[ch[x][1]]+1;
}
int merge(int x, int y) {
if(!x || !y) return x+y;
if(rnd[x] < rnd[y]) {
ch[x][1] = merge(ch[x][1], y);
update(x);
return x;
} else {
ch[y][0] = merge(x, ch[y][0]);
update(y);
return y;
}
}
void split(int cur, int k, int &x, int &y) {
if(!cur) x = y = 0;
else {
if(val[cur] <= k) x = cur, split(ch[cur][1], k, ch[cur][1], y);
else y = cur, split(ch[cur][0], k, x, ch[cur][0]);
update(cur);
}
}
int newNode(int v) {
val[++nid] = v;
sz[nid] = 1;
rnd[nid] = rand();
return nid;
}
void insert(int v) {
int x, y;
split(root, v, x, y);
root = merge(merge(x, newNode(v)), y);
}
void del(int v) {
int x, y, z;
split(root, v, x, z); split(x, v-1, x, y);
y = merge(ch[y][0], ch[y][1]);
root = merge(merge(x, y), z);
}
int rankOf(int v) {
int x, y, ret;
split(root, v-1, x, y);
ret = sz[x]+1;
root = merge(x, y);
return ret;
}
int kth(int src, int x) {
if(sz[src] < x) return 0;
int u = src;
while (1) {
if(x <= sz[ch[u][0]]) u = ch[u][0];
else if(sz[ch[u][0]]+1 == x) return u;
else if(sz[ch[u][0]]+1 < x) x -= sz[ch[u][0]]+1, u = ch[u][1];
}
}
int precursor(int v) { //前驱
int x, y, ret;
split(root, v-1, x, y);
ret = val[kth(x, sz[x])];
root = merge(x, y);
return ret;
}
int successor(int v) { //后继
int x, y, ret;
split(root, v, x, y);
ret = val[kth(y, 1)];
root = merge(x, y);
return ret;
}
int main() {
srand((unsigned)time(NULL));
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1, c, x; i <= n; i++) {
cin >> c >> x;
if(c == 1) insert(x);
else if(c == 2) del(x);
else if(c == 3) cout << rankOf(x) << endl;
else if(c == 4) cout << val[kth(root, x)] << endl;
else if(c == 5) cout << precursor(x) << endl;
else if(c == 6) cout << successor(x) << endl;
}
return 0;
}