评测记录

代码：

#include <bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;

int n, opt, x;
int tot;

template <typename _Ip>
inline void read(_Ip &x) {
    char ch = getchar(), sgn = 0; x = 0;
    while (ch ^ '-' && !isdigit(ch)) ch = getchar();
    if (ch == '-') ch = getchar(), sgn = 1;
    while (isdigit(ch)) x = (x<<3)+(x<<1) + (ch^48), ch = getchar();
    if (sgn) x = -x;
}

template <typename _Op>
inline void write(_Op x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

struct Node {
	int val, pr, ls, rs, cnt, siz;
} tree[500010];

inline void update(int pos) {
	tree[pos].siz = tree[tree[pos].ls].siz + tree[tree[pos].rs].siz + tree[pos].cnt;
}

inline void zig(int &p) {
	int q = tree[p].ls;
	tree[p].ls = tree[q].rs;
	tree[q].rs = p;
	p = q;
	update(tree[p].rs);
	update(p);
}

inline void zag(int &p) {
	int q = tree[p].rs;
	tree[p].rs = tree[q].ls;
	tree[q].ls = p;
	p = q;
	update(tree[p].ls);
	update(p);
}

inline void add(int &p, int v) {
	if (v == tree[p].val) {
		++tree[p].cnt;
		update(p);
		return;
	}
	if (!p) {
		tree[++tot].val = v;
		tree[tot].pr = rand();
		tree[tot].cnt = tree[tot].siz = 1;
		p = tot;
		return;
	}
	if (v < tree[p].val) {
		add(tree[p].ls, v);
		if (tree[p].pr < tree[tree[p].ls].pr) zig(p);
	}
	else if (v > tree[p].val) {
		add(tree[p].rs, v);
		if (tree[p].pr < tree[tree[p].rs].pr) zag(p);
	}
}

inline void remov(int &p, int v) {
	if (!p) return;
	if (v == tree[p].val) {
		if (tree[p].cnt > 1) {
			--tree[p].cnt;
			update(p);
			return;
		}
		if (tree[p].ls || tree[p].rs) {
			if (tree[tree[p].ls].pr > tree[tree[p].rs].pr) {
				zig(p);
				remov(tree[p].rs, v);
			}
			else {
				zag(p);
				remov(tree[p].ls, v);
			}
			update(p);
		}
		else p = 0;
		return;
	}
	else if (v < tree[p].val) remov(tree[p].ls, v);
	else if (v > tree[p].val) remov(tree[p].rs, v);
	update(p);
}

inline int quf(int v) {
	int ans = -INF, p = 1;
	while (p) {
		if (v == tree[p].val) {
			if (tree[p].ls) {
				p = tree[p].ls;
				while (tree[p].rs) p = tree[p].rs;
				ans = tree[p].val;
			}
			break;
		}
		if (tree[p].val < v && tree[p].val > ans) ans = tree[p].val;
		if (tree[p].val < v) p = tree[p].rs;
		else p = tree[p].ls;
	}
	return ans;
}

inline int qub(int v) {
	int ans = INF, p = 1;
	while (p) {
		if (v == tree[p].val) {
			if (tree[p].rs) {
				p = tree[p].rs;
				while (tree[p].ls) p = tree[p].ls;
				ans = tree[p].val;
			}
			break;
		}
		if (tree[p].val > v && tree[p].val < ans) ans = tree[p].val;
		if (tree[p].val < v) p = tree[p].rs;
		else p = tree[p].ls;
	}
	return ans;
}

inline int qup(int p, int v) {
	if (!p) return 0;
	if (v == tree[p].val) return tree[tree[p].ls].siz + 1;
	else if (v < tree[p].val) return qup(tree[p].ls, v);
	else if (v > tree[p].val) return qup(tree[p].rs, v) + tree[tree[p].ls].siz + tree[p].cnt;
}

inline int quv(int p, int v) {
	if ((tree[tree[p].ls].siz+1 <= v) && v <= tree[tree[p].ls].siz+tree[p].cnt) return tree[p].val;
	else if (v <= tree[tree[p].ls].siz) return quv(tree[p].ls, v);
	else return quv(tree[p].rs, v-(tree[tree[p].ls].siz + tree[p].cnt));
}

int main() {
	tree[++tot].val = INF;
	tree[tot].pr = INF;
	read(n);
	int r = 1;
	while (n--) {
		read(opt);read(x);
		if (opt == 1) add(r, x);
		else if (opt == 2) remov(r, x);
		else if (opt == 3) {
			write(qup(r, x));
			putchar('\n');
		}
		else if (opt == 4) {
			write(quv(r, x));
			putchar('\n');
		}
		else if (opt == 5) {
			write(quf(x));
			putchar('\n');
		}
		else if (opt == 6) {
			write(qub(x));
			putchar('\n');
		}
	}
	return 0;
}

刚学 $\text{Treap}$，各位 $\text{dalao}$ 麻烦看看这个模板对吗

另外想再请教一下，听说带旋 $\text{Treap}$ 不太稳定，它和 $\text{FHQ-Treap}$ 哪个更快一些呢？