FHQ Treap模板，采用的是重复键值存放在不同节点中的做法，方便分裂、合并操作。说明见注释，更详细的样例请自行查找网络上带图的文章。

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
struct node {
	int l, r;
	int val, pri;
	int size; // 记录以该节点为根的子树的总节点数
} a[N];
int tot, root, n;

void dbg() {
	printf("root=%d\n", root);
	cout << "idx\tL\tR\tval\tpri\tsize\n";
	for (int i = 1; i <= tot; i++)
		printf("%d\t%d\t%d\t%d\t%d\t%d\n", i, a[i].l, a[i].r, a[i].val, a[i].pri, a[i].size);
}

int New(int val) {
	a[++tot].val = val;
	a[tot].pri = rand();
	a[tot].size = 1;
	return tot;
}

void Update(int p) {
	a[p].size = a[a[p].l].size + a[a[p].r].size + 1;
}

// 优美对称的分裂操作
void Split(int p, int val, int& L, int& R) {
	if (p == 0) {
		L = R = 0;
		return;
	}
	if (a[p].val <= val) {
		L = p;
		Split(a[p].r, val, a[p].r, R);
	} else {
		R = p;
		Split(a[p].l, val, L, a[p].l);
	}
	Update(p);
}

// 优美对称的合并操作
int Merge(int L, int R) {
	if (L == 0 || R == 0) return L + R;
	if (a[L].pri > a[R].pri) {
		a[L].r = Merge(a[L].r, R);
    // 千万别忘了更新！！
		Update(L);
		return L;
	} else {
		a[R].l = Merge(L, a[R].l);
    // // 千万别忘了更新！！
		Update(R);
		return R;
	}
}

int GetRank(int val) {
	int L, R;
	Split(root, val - 1, L, R);
	int res = a[L].size + 1;
  // 千万别忘了合并！！
	root = Merge(L, R);
	return res;
}

// 与普通Treap一样的做法
int GetKthVal(int p, int rnk) {
	if (rnk == a[a[p].l].size + 1) return a[p].val;
	else if (rnk <= a[a[p].l].size) return GetKthVal(a[p].l, rnk);
	else return GetKthVal(a[p].r, rnk - a[a[p].l].size - 1);
}

void Insert(int val) {
	int L, R;
	Split(root, val, L, R);
	int p = New(val);
	int q = Merge(L, p);
	root = Merge(q, R);
}

void Remove(int val) {
	int L, R, p;
	Split(root, val, L, R);
	Split(L, val - 1, L, p);
	// 只删除一个val节点，可能会有多个重复的val，
	// 那么需要把这些重复的val节点合成一棵树
	p = Merge(a[p].l, a[p].r);
	root = Merge(Merge(L, p), R);
}

int GetPre(int val) {
	int L, R;
	Split(root, val - 1, L, R);
	if (L == 0) return 0x80000000;

	int res = GetKthVal(L, a[L].size);
	root = Merge(L, R); // 千万别忘了合并！！
	return res;
}

int GetSucc(int val) {
	int L, R;
	Split(root, val, L, R);
	if (R == 0) return 0x7fffffff;

	int res = GetKthVal(R, 1);
	root = Merge(L, R); // 千万别忘了合并！！
	return res;
}

int main() {
	srand(time(nullptr));
	cin >> n;
	while (n--) {
		int op, x;
		cin >> op >> x;
		if (op == 1) Insert(x);
		else if (op == 2) Remove(x);
		else if (op == 3) cout << GetRank(x) << '\n';
		else if (op == 4) cout << GetKthVal(root, x) << '\n';
		else if (op == 5) cout << GetPre(x) << '\n';
		else cout << GetSucc(x) << '\n';
	}

	return 0;
}

普通Treap模板，结合了李煜东和《算法竞赛》的写法。说明见注释。

#include <iostream>
using namespace std;

const int N = 1e5 + 10, INF = 0x7fffffff;
struct node {
	int l, r;
	int val, dat;
	int cnt, size; //cnt记录键值的重复次数，size记录以该节点为根的子树的总节点数。
} a[N];
int tot, root, n;
// 与BST相比，Treap很重要的一个数据就是整棵树的树根root！
// 因为在旋转过程中树的形态很可能会改变，所以一定要记录根！！！

int New(int val) {
	a[++tot].val = val;
	a[tot].dat = rand();
	a[tot].cnt = a[tot].size = 1;
	return tot;
}

void Update(int p) {
	a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;
}

void Build() {
	New(-INF), New(INF);
	root = 1, a[1].r = 2;
	Update(root);
}

int GetRank(int p, int val) {
	if (p == 0) return 0;
	if (val == a[p].val) return a[a[p].l].size;
	else if (val < a[p].val) return GetRank(a[p].l, val);
	else return GetRank(a[p].r, val) + a[a[p].l].size + a[p].cnt;
}

int GetVal(int p, int rnk) {
	if (p == 0) return INF;
	if (a[a[p].l].size >= rnk) return GetVal(a[p].l, rnk);
	else if (a[a[p].l].size + a[p].cnt >= rnk) return a[p].val;
	else return GetVal(a[p].r, rnk - a[a[p].l].size - a[p].cnt);
}

// 右旋。建议改成你记得住的、不会弄混左右的名字。
// 可以这样理解记忆右旋：节点p变成自己右孩子的孩子。
void Zig(int& p) {
	int q = a[p].l;
	a[p].l = a[q].r, a[q].r = p, p = q;
	Update(a[p].r), Update(p);
}

// 左旋。建议改成你记得住的、不会弄混左右的名字。
// 可以这样理解记忆左旋：节点p变成自己左孩子的孩子。
void Zag(int& p) {
	int q = a[p].r;
	a[p].r = a[q].l, a[q].l = p, p = q;
	Update(a[p].l), Update(p);
}

void Insert(int& p, int val) {
	if (p == 0) {
		p = New(val);
		return;
	}
	if (val == a[p].val) a[p].cnt++;
	else if (val < a[p].val) {
		Insert(a[p].l, val);
		if (a[p].dat < a[a[p].l].dat) Zig(p);
	} else {
		Insert(a[p].r, val);
		if (a[p].dat < a[a[p].r].dat) Zag(p);
	}
	Update(p);
}

void Remove(int& p, int val) {
	if (p == 0) return;
	if (val == a[p].val) {
		if (a[p].cnt > 1) {
			a[p].cnt--, Update(p);
			return;
		}
		if (a[p].l || a[p].r) {
			if (a[p].r == 0 || a[a[p].l].dat > a[a[p].r].dat)
				Zig(p), Remove(a[p].r, val);
			else Zag(p), Remove(a[p].l, val);
			Update(p);
		} else p = 0;
		return;
	}
	val < a[p].val ? Remove(a[p].l, val) : Remove(a[p].r, val);
	Update(p);
}

int GetPre(int val) {
	int ans = 1, p = root;
	while (p) {
		// 当前比val小的这个节点可能是val的前驱，所以用ans记一下
		if (a[p].val < val) ans = p, p = a[p].r;
		else p = a[p].l;
	}
	return a[ans].val;
}

int GetSucc(int val) {
	int ans = 1, p = root;
	while (p) {
		if (a[p].val > val) ans = p, p = a[p].l;
		else p = a[p].r;
	}
	return a[ans].val;
}

int main() {
	Build();
	cin >> n;
	while (n--) {
		int op, x;
		cin >> op >> x;
		if (op == 1) Insert(root, x);
		else if (op == 2) Remove(root, x);
		else if (op == 3) cout << GetRank(root, x) << '\n';
		else if (op == 4) cout << (GetVal(root, x + 1)) << '\n';
		else if (op == 5) cout << GetPre(x) << '\n';
		else cout << GetSucc(x) << '\n';
	}

	return 0;
}

FHQ-Treap学习心得

建议大家把学习复杂模板过程中遇到的问题和经验记录下来，专门放到一个博客里或者随题目放到题解里（以示后人），不然过段时间以后就忘掉了，然后遇到相同问题时痛苦地回忆半天想不起来。

心得1

FHQ-Treap不太适合用一个cnt域来记录重复键值，因为这会导致插入、删除等多处代码不优美，要写if分类讨论，很容易写错。例如下面这棵Treap：

10
 \
  20

若采用cnt域来记录重复键值，那么当插入20时，先Split出来的两棵树的根，L是节点10，R是空，那么还得写个循环找到L子树的最右下角节点是否为20。

结论：如果想把FHQ-Treap的代码写得更优美，建议不要用cnt存重复键值，每个键值新建一个节点即可。

（未完待续）