Treap板子58pts求调，WA #7~#12

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n, root = 0;
struct node {
	int val, pri;
	int cnt, size;
	int lc, rc;
} nd[MAXN];
int num_node;
int New(int val) {
	num_node++;
	nd[num_node].lc = nd[num_node].rc = 0;
	nd[num_node].val = val;
	nd[num_node].pri = rand();
	nd[num_node].cnt = 1;
	nd[num_node].size = 1;
	return num_node;
}
void Update(int k) {
	nd[k].size = nd[nd[k].lc].size + nd[k].cnt + nd[nd[k].rc].size;
}
void zig(int &p) { //right
	int q = nd[p].lc;
	nd[p].lc = nd[q].rc;
	nd[q].rc = p;
	Update(p);
	Update(q);
	p = q;
}
void zag(int &p) { //left
	int q = nd[p].rc;
	nd[p].rc = nd[q].lc;
	nd[q].lc = p;
	Update(p);
	Update(q);
	p = q;
}
void Insert(int &p, int val) {
	if (p == 0) {
		p = New(val);
		return;
	}
	if (nd[p].val > val) {
		Insert(nd[p].lc, val);
		Update(p);
		if (nd[nd[p].lc].pri > nd[p].pri)zig(p);
	} else if (nd[p].val == val) {
		nd[p].cnt++;
		Update(p);
	} else {
		Insert(nd[p].rc, val);
		Update(p);
		if (nd[nd[p].rc].pri > nd[p].pri)zag(p);
	}
}
void Del(int &p, int val) {
	if (p == 0)return;
	if (nd[p].val > val) {
		Del(nd[p].lc, val);
		Update(p);
	} else if (nd[p].val < val) {
		Del(nd[p].rc, val);
		Update(p);
	} else if (nd[p].val == val) {
		if (nd[p].cnt > 1) {
			nd[p].cnt--;
			Update(p);
			return;
		} else if (nd[p].lc == 0 || nd[p].rc == 0) {
			p = nd[p].lc + nd[p].rc;
			return;
		} else {
			if (nd[nd[p].lc].pri > nd[nd[p].rc].pri) {
				zig(p);
				Del(nd[p].rc, val);
			} else {
				zag(p);
				Del(nd[p].lc, val);
			}
		}
	}
}
int Rank(int p, int val) {
	if (p == 0)return 1;
	if (nd[p].val > val)return Rank(nd[p].lc, val);
	if (nd[p].val == val)return nd[nd[p].lc].size + 1;
	else {
		return nd[nd[p].lc].size + nd[p].cnt + Rank(nd[p].rc, val);
	}
}
int find_r(int p, int rank) {
	if (p == 0)return 0;
	if (nd[nd[p].lc].size >= rank)return find_r(nd[p].lc, rank);
	if (nd[nd[p].lc].size + nd[p].cnt >= rank)return nd[p].val;
	else {
		return find_r(nd[p].rc, rank - nd[nd[p].lc].size - nd[p].cnt);
	}
}
int find_p(int val) {
	int p = root, ans = -1e7;
	while (p != 0 && nd[p].val != val) {
		if (nd[p].val < val) {
			ans = max(ans, nd[p].val);
			p = nd[p].rc;
		}
		if (nd[p].val > val)p = nd[p].lc;
	}
	p = nd[p].lc;
	while (p) {
		ans = max(ans, nd[p].val);
		p = nd[p].rc;
	}
	return ans;
}
int find_n(int val) {
	int p = root, ans = 1e7;
	while (p != 0 && nd[p].val != val) {
		if (nd[p].val < val)p = nd[p].rc;
		if (nd[p].val > val) {
			ans = min(ans, nd[p].val);
			p = nd[p].lc;
		}
	}
	p = nd[p].rc;
	while (p) {
		ans = min(ans, nd[p].val);
		p = nd[p].lc;
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	srand(time(NULL));
	for (int i = 1; i <= n; i++) {
		int opt, x;
		cin >> opt >> x;
		switch (opt) {
			case 1:
				Insert(root, x);
				break;
			case 2:
				Del(root, x);
				break;
			case 3:
				cout << Rank(root, x) << "\n";
				break;
			case 4:
				cout << find_r(root, x) << "\n";
				break;
			case 5:
				cout << find_p(x) << "\n";
				break;
			case 6:
				cout << find_n(x) << "\n";
				break;
		}
	}
	return 0;
}