Splay, 52pts 求助 /kk

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
struct Node {
	int s[2], fa, val, siz, cnt;
	Node() {
		s[0] = s[1] = 0; fa = 0;
	}
} t[1000010];
int tot;
void pushup(int u) {
	t[u].siz = t[t[u].s[0]].siz + t[t[u].s[1]].siz + t[u].cnt;
}
int getdir(int u) {
	return u == t[t[u].fa].s[1];
}
void link(int u, int dir, int v) {
	if (u) t[u].s[dir] = v; if (v) t[v].fa = u;
}
void rota(int x) {
	int y = t[x].fa, z = t[y].fa, dir = getdir(x);
	link(z, getdir(y), x);
	link(y, dir, t[x].s[dir ^ 1]);
	link(x, dir ^ 1, y);
	pushup(y), pushup(x);
}
int rt;
void splay(int x, int s) {
	while (t[x].fa != s) {
		int y = t[x].fa, z = t[y].fa;
		if (z != s) {
			if (getdir(x) == getdir(y)) rota(y); else rota(x); 
		}
		rota(x);
	}
	if (!s) rt = x;
}
int ins(int u, int x, int f) {
	if (!u) {
		++tot; t[tot].cnt = 1; t[tot].val = x; t[tot].fa = f; t[f].s[x > t[f].val] = tot; pushup(tot); return tot;
	}
	if (t[u].val == x) {
		++t[u].cnt; pushup(u); return u;
	}
	int g = ins(t[u].s[x > t[u].val], x, u); pushup(u); return g;
}
void insert(int x) {
	splay(ins(rt, x, 0), 0);
}
int del(int u, int x) {
	if (t[u].val == x) {
		--t[u].cnt; pushup(u); return u;
	}
	int g = del(t[u].s[x > t[u].val], x); pushup(u); return g;
}
void delet(int x) {
	splay(del(rt, x), 0);
}
int getrk(int u, int x) {
	if (!u) return 1;
	if (t[u].val == x) {
		int c = t[t[u].s[0]].siz + 1;
		splay(u, 0); return c;
	}
	int d = t[t[u].s[0]].siz + t[u].cnt;
	if (t[u].val > x) return getrk(t[u].s[0], x); else return getrk(t[u].s[1], x) + d;
}
int getval(int u, int k) {
	int x = t[t[u].s[0]].siz;
	if (k == x + 1) {
		int D = t[u].val;
		splay(u, 0); return D;
	}
	if (k <= x) return getval(t[u].s[0], k); else return getval(t[u].s[1], k - x - t[u].cnt); 
}
int findpre(int x) {
	return getval(rt, getrk(rt, x) - 1);
}
int findlas(int x) {
	return getval(rt, getrk(rt, x + 1));
}
signed main() {
	int q;
	cin >> q;
	while (q--) {
		int op;
		int x;
		cin >> op >> x;
		if (op == 1) insert(x);
		else if (op == 2) delet(x);
		else if (op == 3) cout << getrk(rt, x) << "\n";
		else if (op == 4) cout << getval(rt, x) << "\n";
		else if (op == 5) cout << findpre(x) << "\n";
		else cout << findlas(x) << "\n";
	}
	return 0;   
}