有旋Treap求调 79ptsWa#10-#12

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int Mod = 998244353, mod = 1e9 + 7, N = 1e5 + 10;
int cnt, n, rt;
struct no{
	int l, r, pri, key, size;
} tree[N];
void update(int x) {tree[x].size = tree[tree[x].l].size + tree[tree[x].r].size + 1;}
void rotate(int& o, int op) {
	int x = op ? tree[o].r : tree[o].l;
	if (op) tree[o].r = tree[x].l, tree[x].l = o;
	else tree[o].l = tree[x].r, tree[x].r = o;
	update(x), update(o), o = x;
}
void insert(int &u, int x) {
	if (!u) {tree[u = ++cnt] = {0, 0, rand(), x, 1}; return;}
	tree[u].size++;
	x < tree[u].key ? insert(tree[u].l, x) : insert(tree[u].r, x);
	if (tree[u].l && tree[u].pri > tree[tree[u].l].pri) rotate(u, 0);
	if (tree[u].r && tree[u].pri > tree[tree[u].r].pri) rotate(u, 1);
	update(u);
}
void del(int &u, int x) {
	if (!u) return;
	if (tree[u].key == x) {
		if (!tree[u].l || !tree[u].r) u = tree[u].l + tree[u].r;
		else tree[tree[u].l].pri < tree[tree[u].r].pri ? rotate(u, 0), del(tree[u].r, x) : rotate(u, 1), del(tree[u].l, x);
		if(u) update(u);
		return;
	}
	x <= tree[u].key ? del(tree[u].l, x) : del(tree[u].r, x);
	update(u);
}
int rk(int u, int x) {
	if (!u) return 0;
	return x <= tree[u].key ? rk(tree[u].l, x) : tree[tree[u].l].size + 1 + rk(tree[u].r, x);
}
int kth(int u, int x) {
	if (x == tree[tree[u].l].size + 1) return tree[u].key;
	return x <= tree[tree[u].l].size ? kth(tree[u].l, x) : kth(tree[u].r, x - tree[tree[u].l].size - 1);
}
int pre(int u, int x) {
	if (!u) return -1e9;
	if (x > tree[u].key) {
		int t = pre(tree[u].r, x);
		return max(t, tree[u].key);
	}
	return pre(tree[u].l, x);
}
int suf(int u, int x) {
	if (!u) return 1e9;
	if (x < tree[u].key) {
		int t = suf(tree[u].l, x);
		return min(t, tree[u].key);
	}
	return suf(tree[u].r, x);
}

int main() {
	cin.tie(0) -> ios::sync_with_stdio(false);
	srand(time(0));
	cin >> n;
	while(n--) {
		int op, x;
		cin >> op >> x;
		if (op == 1) insert(rt, x);
		if (op == 2) del(rt, x);
		if (op == 3) cout << rk(rt, x) + 1 << endl;
		if (op == 4) cout << kth(rt, x) << endl;
		if (op == 5) cout << pre(rt, x) << endl;
		if (op == 6) cout << suf(rt, x) << endl;
	}
	return 0;
}