题目链接：https://www.luogu.org/problemnew/show/P3369
#include <cstdio>
#include <algorithm>
#include <iostream>
#define ri register
#define il inline
using namespace std;
const int maxn = 1000000;
struct RNG{
int fa, cnt, v, sub, son[2];
}e[maxn];
int root, n, m, whole_size;
il void Clear(int x){
e[x].cnt = e[x].fa = e[x].son[0] = e[x].son[1] = e[x].sub = e[x].v = 0;
}
il bool Get_which(int x){
return e[e[x].fa].son[1] == x;
}
il void update(int x){
if(x){
e[x].sub = e[x].cnt;
if(e[x].son[0]) e[x].sub += e[e[x].son[0]].sub;
if(e[x].son[1]) e[x].sub += e[e[x].son[1]].sub;
}
return;
}
il void rotate(int x){
int father = e[x].fa, get_father = e[father].fa, which_son = Get_which(x);
e[father].son[which_son] = e[x].son[which_son^1];
e[e[father].son[which_son]].fa = father;
e[x].son[which_son^1] = father;
e[father].fa = x;
e[x].fa = get_father;
if(get_father){
e[get_father].son[e[get_father].son[1]==father] = x;
}
update(father);
update(x);
return;
}
il void splay(int x){
for(int fa; fa = e[x].fa; rotate(x))
if(e[fa].fa)
rotate((Get_which(x) == Get_which(fa)) ? fa : x);
root = x;
return;
}
il void insert(int x){
if(!root){
whole_size++;
e[whole_size].son[0] = e[whole_size].son[1] = e[whole_size].fa = 0;
root = whole_size;
e[whole_size].sub = e[whole_size].cnt++;
e[whole_size].v = x;
return;
}
int now = root, fa = 0;
while(1)
{
if(x == e[now].v){
e[now].cnt++;
update(now);
update(fa);
splay(now);
break;
}
fa = now;
now = e[now].son[e[now].v < x];
if(!now){
whole_size++;
e[whole_size].son[0] = e[whole_size].son[1] = 0;
e[whole_size].fa = fa;
e[whole_size].sub = e[whole_size].cnt = 1;
e[fa].son[e[fa].v<x] = whole_size;
e[whole_size].v = x;
update(fa);
splay(whole_size);
break;
}
}
return;
}
il int Find_num(int x){
int now = root;
while(1){
if(e[now].son[0]&&x<=e[e[now].son[0]].sub)
now = e[now].son[0];
else{
int temp = (e[now].son[0]?e[e[now].son[0]].sub:0)+e[now].cnt;
if(x <= temp) return e[now].v;
x-=temp;
now = e[now].son[1];
}
}
}
il int Find_rank(int x){
int now = root, ans = 0;
while(1){
if(x<e[now].v)
now = e[now].son[0];
else{
ans += (e[now].son[0]?e[e[now].son[0]].sub:0);
if(x == e[now].v){
splay(now); return ans+1;
}
ans += e[now].cnt;
now = e[now].son[1];
}
}
}
il int Find_pre(){
int now = e[root].son[0];
while(e[now].son[1]) now = e[now].son[1];
return now;
}
il int Find_suffix(){
int now = e[root].son[1];
while(e[now].son[0]) now = e[now].son[0];
return now;
}
il void Delete(int x)
{
int hhh = Find_rank(x);
if(e[root].cnt>1){
e[root].cnt--;
update(root);
return;
}
if(!e[root].son[0]&&!e[root].son[1]){
Clear(root);
root = 0;
return;
}
if(!e[root].son[0]){
int old_root = root;
root = e[root].son[1];
e[root].fa = 0;
Clear(old_root);
return;
}
else if(!e[root].son[1]){
int old_root = root;
root = e[root].son[0];
e[root].fa = 0;
Clear(old_root);
return;
}
int left_max = Find_pre(), old_root = root;
splay(left_max);
e[root].son[1] = e[old_root].son[1];
e[e[old_root].son[1]].fa = root;
Clear(old_root);
update(root);
return ;
}
int main(){
int m, num, be_dealt;
scanf("%d",&m);
for(int i = 1; i <= m; i++){
scanf("%d%d",&num,&be_dealt);
if(num == 1){insert(be_dealt);}
if(num == 2){Delete(be_dealt);}
if(num == 3){printf("%d\n",Find_rank(be_dealt));}
if(num == 4){printf("%d\n",Find_num(be_dealt));}
if(num == 5){
insert(be_dealt);
printf("%d\n",e[Find_pre()].v);
Delete(be_dealt);}
if(num == 6){
insert(be_dealt);
printf("%d\n",e[Find_suffix()].v);
Delete(be_dealt);
}
}
return 0;
}