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
| #include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5+2;
struct Splay {
struct node {
node *ch[2], *fa; int val, size;
node (node *fa = NULL, int val = 0) : fa(fa), val(val) {ch[0] = ch[1] = NULL; size = 1;}
inline bool isr () { return fa -> ch[1] == this;}
inline bool up () { size = (ch[0] ? ch[0] -> size : 0) + (ch[1] ? ch[1] -> size : 0) + 1;}
inline int rnk () { return (ch[0] ? ch[0] -> size : 0) + 1;}
}*root, pool[N], *tail, *st[N];
int top;
Splay () { tail = pool; root = NULL; top = 0;}
inline void rot (node *x) {
int k = x -> isr();
node *y = x -> fa, *z = y -> fa, *w = x -> ch[!k];
if (y == root) root = x; else z -> ch[y->isr()] = x;
x -> fa = z, y -> fa = x;
x -> ch[!k] = y, y -> ch[k] = w;
if (w) w -> fa = y;
y -> up(); x -> up();
}
inline void splay (node *x) {
while (x != root) {
if (x -> fa != root) rot (x -> isr() ^ x -> fa -> isr() ? x : x -> fa);
rot (x);
}
}
inline void Insert (int val) {
if (!root) return (void) (root = new (tail ++) node (NULL, val));
node *x = root, *fa = NULL;
while (x) {
fa = x;
x = x -> ch[val > x -> val];
}
x = new (tail ++) node (fa, val);
fa -> ch[val > fa -> val] = x; splay (x);
}
node *merge (node *x, node *y, node *fa) {
if (x) x -> fa = fa;
if (y) y -> fa = fa;
if (!x || !y) return x ? x : y;
return x -> ch[1] = merge (x -> ch[1], y, x), x -> up(), x;
}
inline void del (int val) {
node *x = root;
while (x && x -> val != val) x = x -> ch[val > x -> val];
if (x == NULL) return;
splay(x);
root = merge (x -> ch[0], x -> ch[1], NULL);
st[++top] = x, x = NULL;
}
inline int rnk (int val) {
node *x = root, *last = NULL; int res = 0;
while (x) {
last = x;
if (val <= x -> val) x = x -> ch[0];
else res += x -> rnk(), x = x -> ch[1];
}
return splay(last), res + 1;
}
inline int kth (int k) {
node *x = root;
while (x && x -> rnk() != k) {
if (x -> rnk() > k) x = x -> ch[0];
else k -= x -> rnk(), x = x -> ch[1];
}
return splay (x), x -> val;
}
inline int pre (int x) {return kth(rnk(x)-1);}
inline int nxt (int x) {return kth(rnk(x+1));}
inline void Action () {
int t;
scanf ("%d", &t);
while (t --> 0) {
int opt, x;
scanf ("%d%d", &opt, &x);
if (opt == 1) Insert (x);
if (opt == 2) del (x);
if (opt == 3) printf ("%d\n", rnk(x));
if (opt == 4) printf ("%d\n", kth(x));
if (opt == 5) printf ("%d\n", pre(x));
if (opt == 6) printf ("%d\n", nxt(x));
}
}
}yhm;
int main () { return yhm.Action(), 0;}
|