CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct FhqTreap
{
struct Node
{
int ch[2],siz;
ll key,val;
};
vector<Node> v;
int root;
FhqTreap():v(1),root(0) {}
void push_up(int k)
{
v[k].siz=v[v[k].ch[0]].siz+v[v[k].ch[1]].siz+1;
}
int merge(int a,int b)
{
if(!a||!b)return a+b;
if(v[a].key<v[b].key)
return v[a].ch[1]=merge(v[a].ch[1],b),push_up(a),a;
return v[b].ch[0]=merge(a,v[b].ch[0]),push_up(b),b;
}
void splitVal(int a,ll w,int &l,int &r)//按值将树划分，使得左子树上的值恰小于w
{
if(!a)l=r=0;
else if(v[a].val>w)splitVal(v[a].ch[0],w,l,v[a].ch[0]),push_up(r=a);
else splitVal(v[a].ch[1],w,v[a].ch[1],r),push_up(l=a);
}
void insert(ll x)
{
int a,b;
v.push_back(Node { {0,0},1,rand(),x});
splitVal(root,x,a,b),root=merge(merge(a,v.size()-1),b);
}
void erase(ll x)
{
int a,b,c;
splitVal(root,x,a,b),splitVal(a,x-1,a,c);
root=merge(merge(a,merge(v[c].ch[0],v[c].ch[1])),b);
}
ll kth(int k)
{
for(int u=root,ls;;)
{
if(ls=v[v[u].ch[0]].siz,ls+1==k)
return v[u].val;
if(ls<k)k-=ls+1,u=v[u].ch[1];
else u=v[u].ch[0];
}
}
int lower_bound(ll x)
{
return upper_bound(x-1);
}
int upper_bound(ll x)
{
int a,b,ret;
return splitVal(root,x,a,b),ret=v[a].siz+1,root=merge(a,b),ret;
}
};
int main()
{
int n,o,x;
FhqTreap t;
for(scanf("%d",&n); n--;)
{
scanf("%d%d",&o,&x);
if(o==1)t.insert(x);
else if(o==2)t.erase(x);
else printf("%d\n",o==3?t.lower_bound(x):
t.kth(o==4?x:
o==5?t.lower_bound(x)-1:
t.upper_bound(x)));
}
}