rt.挂掉40分/kk

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 0x7fffffff;

struct node {
	node *fa, *son[2];
	node(node *fa = nullptr, int val = 0): fa(fa), val(val) { memset(son, 0, sizeof son), size = cnt = 1; }
	int val, size, cnt;
};

typedef node *nodeptr;

nodeptr root = nullptr;

inline 
void pushup(nodeptr x) {
	x->size = x->cnt;
	if (x->son[0]) x->size += x->son[0]->size;
	if (x->son[1]) x->size += x->son[1]->size;
}

inline 
void rotate(nodeptr x) {
	nodeptr y = x->fa, z = y->fa;
	bool c = (y->son[0] == x);
	y->son[!c] = x->son[c];
	if (x->son[c]) x->son[c]->fa = y;
	x->fa = z;
	if (z) z->son[z->son[1] == y] = x; 
	x->son[c] = y, y->fa = x;
	pushup(y), pushup(x);
}

inline 
void splay(nodeptr x, nodeptr rt) {
	while (x->fa != rt) {
		nodeptr y = x->fa, z = y->fa;
		if (z != rt) rotate((z->son[0] == y) ^ (y->son[0] == x) ? x : y);
		rotate(x);
	}
	if (!rt) root = x;
}

inline 
void insert(int val) {
	nodeptr k = root, fa = nullptr;
	while (k && k->val != val) fa = k, k = k->son[k->val < val];
	if (k) return k->cnt++, splay(k, 0), void();
	k = new node(fa, val);
	if (fa) fa->son[fa->val < val] = k;
	splay(k, 0);
}

inline 
void find(int val) {
	nodeptr x = root;
	if (!x) return ;
	while (x->son[x->val < val] && val != x->val) x = x->son[x->val < val];
	splay(x, 0);
}

inline 
nodeptr get(int val, bool f) {
	find(val);
	nodeptr x = root;
	if ((x->val > val && f) || (x->val < val && !f)) return x;
	x = x->son[f];
	while (x->son[!f]) x = x->son[!f];
	return x;
}

inline 
nodeptr findk(int k) {
	nodeptr x = root;
	if (x->size < k) return new node();
	while (1) {
		int rnk = x->son[0] ? x->son[0]->size : 0;
		if (k > rnk + x->cnt) k -= rnk + x->cnt, x = x->son[1];
		else if (k <= rnk) x = x->son[0];
		else return x;
	}
}

inline 
void erase(int val) {
	nodeptr x = get(val, 0), y = get(val, 1);
	splay(x, 0), splay(y, x);
	if (y->son[0]->cnt > 1) y->son[0]->cnt--, splay(y->son[0], 0);
	else delete y->son[0], y->son[0] = nullptr, splay(y, 0);
}

void check(nodeptr x) {
	int k = x->cnt;
	if (x->son[0]) k += x->son[0]->size, check(x->son[0]);
	if (x->son[1]) k += x->son[1]->size, check(x->son[1]);
}

void print(nodeptr x) {
	if (x->son[0]) print(x->son[0]);
	for (int i = 1; i <= x->cnt; i++) printf("%d ", x->val);
	if (x->son[1]) print(x->son[1]);
}

int n, m, cnt;

int opt, x;

int main() {
	insert(-inf), insert(inf), cnt += 2;
    for (scanf("%d", &n); n--;) {
		scanf("%d%d", &opt ,&x);
		switch (opt) {
		case 1: insert(x), cnt++; break;
		case 2: erase(x), cnt--; break;
		case 3: find(x), printf("%d\n", root->son[0]->size); break;
		case 4: printf("%d\n", findk(x + 1)->val); break;
		case 5: printf("%d\n", get(x, 0)->val); break;
		case 6: printf("%d\n", get(x, 1)->val); break;
		}
	}
}