放一个一知半解的抄的板子
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
int Case = 1;
struct node{
int ch[2];
int fa, val, cnt, size;
}tr[maxn];
int root, tot;
void pushup(int u) {
tr[u].size = tr[tr[u].ch[0]].size + tr[tr[u].ch[1]].size+tr[u].cnt;
}
void rotate(int x) {
int y = tr[x].fa;
int z = tr[y].fa;
int k = (tr[y].ch[1] == x);
tr[z].ch[tr[z].ch[1] == y] = x;
tr[x].fa = z;
tr[y].ch[k] = tr[x].ch[k^1];
tr[tr[x].ch[k^1]].fa = y;
tr[x].ch[k^1] = y;
tr[y].fa = x;
pushup(y);pushup(x);
}
void splay(int x, int goal) {
while(tr[x].fa != goal) {
int y = tr[x].fa, z = tr[y].fa;
if(z != goal)
(tr[y].ch[0] == x)^(tr[z].ch[0] == y) ?rotate(x):rotate(y);
rotate(x);
}
if(goal == 0) root = x;
}
void find(int x) {
int u = root;
if(!u) return;
while(tr[u].ch[x>tr[u].val] && x != tr[u].val)
u = tr[u].ch[x>tr[u].val];
splay(u, 0);
}
void insert(int x) {
int u = root, fa = 0;
while(u&&tr[u].val != x) {
fa = u;
u = tr[u].ch[x>tr[u].val];
}
if(u) tr[u].cnt++;
else {
u = ++tot;
if(fa) tr[fa].ch[x>tr[fa].val] = u;
tr[u].ch[0] = tr[u].ch[1] = 0;
tr[tot].fa = fa;
tr[tot].val = x;
tr[tot].cnt = 1;
tr[tot].size = 1;
}
splay(u, 0);
}
int Next(int x, int f) {
find(x);
int u = root;
if(tr[u].val>x&&f)return u;
if(tr[u].val<x&&!f) return u;
u = tr[u].ch[f];
while(tr[u].ch[f^1]) u = tr[u].ch[f^1];
return u;
}
void Delete(int x) {
int last = Next(x, 0);
int next = Next(x, 1);
splay(last, 0);splay(next, last);
int del = tr[next].ch[0];
if(tr[del].cnt>1){
tr[del].cnt--;
splay(del, 0);
}
else tr[next].ch[0] = 0;
}
int kth(int x) {
int u = root;
if(tr[u].size<x)
return 0;
while(1) {
int y = tr[u].ch[0];
if(x>tr[y].size+tr[u].cnt) {
x -= tr[y].size + tr[u].cnt;
u = tr[u].ch[1];
}
else
if(tr[y].size>=x)
u = y;
else return tr[u].val;
}
}
void solve() {
int n, m;
scanf("%d", &n);
insert(2000000001);
insert(-2000000001);
for(int i = 1; i <= n; i++) {
int op, x;scanf("%d%d", &op, &x);
if(op == 1)
insert(x);
else if(op == 2)
Delete(x);
else if(op == 3) {
find(x);
printf("%d\n", tr[tr[root].ch[0]].size);
}
else if(op == 4)
printf("%d\n", kth(x+1));
else if(op == 5)
printf("%d\n", tr[Next(x, 0)].val);
else if(op == 6)
printf("%d\n", tr[Next(x, 1)].val);
}
return;
}
int main() {
while(Case--) {
solve();
}
return 0;
}