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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| #include<cstdio>
#include<algorithm>
using namespace std;
#define re register
const int MAXn = 1e4;
const int INF = 2147483647;
template <class T>
inline void read(T &a) {
register char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());register bool f = c == '-';register T s = f ? 0 : c - '0';for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {s = (s << 3) + (s << 1) + c - '0';}a = f ? -s : s;
}
struct Node {
int l, r, siz, cnt, val;
};
Node nd[MAXn + 10];
int cnt;
void Insert(int id, int val) {
++nd[id].siz;
if (nd[id].val == val) {
++nd[id].cnt;
} else if (nd[id].val < val) {
if (!nd[id].r) {
nd[++cnt].val = val;
nd[id].r = cnt;
}
Insert(nd[id].r, val);
} else {
if (!nd[id].l) {
nd[++cnt].val = val;
nd[id].l = cnt;
}
Insert(nd[id].l, val);
}
}
int ValtoRank(int id, int val) {
if (!id) {
return 1;
}
if (nd[id].val == val) {
return nd[nd[id].l].siz + 1;
} else if (nd[id].val < val) {
return nd[nd[id].l].siz + nd[id].cnt + ValtoRank(nd[id].r, val);
} else {
return ValtoRank(nd[id].l, val);
}
}
int RanktoVal(int id, int rank) {
if (!id) {
return -123456789;
}
if (rank <= nd[nd[id].l].siz) {
return RanktoVal(nd[id].l, rank);
} else if (rank > nd[nd[id].l].siz + nd[id].cnt) {
return RanktoVal(nd[id].r, rank - nd[nd[id].l].siz - nd[id].cnt);
} else {
return nd[id].val;
}
}
int EvaPreVal(int id, int val) {
if (!id) {
return -INF;
}
if (nd[id].val >= val) {
return EvaPreVal(nd[id].l, val);
} else {
return max(nd[id].val, EvaPreVal(nd[id].r, val));
}
}
int EvaNexVal(int id, int val) {
if (!id) {
return INF;
}
if (nd[id].val <= val) {
return EvaNexVal(nd[id].r, val);
} else {
return min(nd[id].val, EvaNexVal(nd[id].l, val));
}
}
int root = 1, n, opt, x;
int main() {
read(n);
nd[1].cnt = 1; nd[1].l = 2; nd[1].siz = 2; nd[1].val = INF;
nd[2].cnt = 1; nd[2].siz = 1; nd[2].val = -INF;
cnt += 2;
for (re int i = 1; i <= n; ++i) {
read(opt), read(x);
switch (opt) {
case 1:
printf("%d\n", ValtoRank(root, x) - 1);
break;
case 2:
printf("%d\n", RanktoVal(root, x + 1));
break;
case 3:
printf("%d\n", EvaPreVal(root, x));
break;
case 4:
printf("%d\n", EvaNexVal(root, x));
break;
case 5:
Insert(root, x);
break;
}
}
}
|
