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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
| #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100005;
int n, cnt;
struct Treap{
Treap *L, *R;
int fix, val, size;
void Init() { L = R = NULL; }
inline int lsize() { return L ? L->size : 0; }
inline int rsize() { return R ? R->size : 0; }
} Node[N], *root;
Treap * NewNode() {
Node[cnt].Init();
return Node + (cnt++);
}
void Recount(Treap * &p) {
p->size = p->lsize() + p->rsize() + 1;
}
void Treap_R_Rot(Treap *&a) {
Treap *b = a->L;
a->L = b->R;
b->R = a;
a = b;
Recount(a->R);
Recount(a);
}
void Treap_L_Rot(Treap *&a) {
Treap *b = a->R;
a->R = b->L;
b->L = a;
a = b;
Recount(a->L);
Recount(a);
}
void Treap_insert(Treap *&p, int val) {
if(p == NULL) {
p = NewNode();
p->val = val;
p->size = 1;
p->fix = rand();
} else if(val <= p->val) {
p->size++;
Treap_insert(p->L, val);
if(p->L->fix < p->fix) Treap_R_Rot(p);
} else {
p->size++;
Treap_insert(p->R, val);
if(p->R->fix < p->fix) {
Treap_L_Rot(p);
}
}
}
void Treap_Del(Treap * &p, int val) {
if(val == p->val) {
if(!p->L || !p->R) {
if (p->L) p = p->L;
else p = p->R;
} else if(p->L->fix < p->R->fix) {
Treap_R_Rot(p);
p->size--;
Treap_Del(p->R, val);
} else {
Treap_L_Rot(p);
p->size--;
Treap_Del(p->L, val);
}
} else if(val < p->val) {
p->size--;
Treap_Del(p->L, val);
} else {
p->size--;
Treap_Del(p->R, val);
}
}
int Treap_Rank(Treap *p, int val) {
if(!p) return 0;
if(val > p->val) return p->lsize() + Treap_Rank(p->R, val) + 1;
else return Treap_Rank(p->L, val);
}
int Treap_Find(Treap *p, int rank) {
if(p->lsize()+1 == rank)
return p->val;
if(p->lsize()+1 > rank)
return Treap_Find(p->L, rank);
else
return Treap_Find(p->R, rank - p->lsize() - 1);
}
int Treap_pre(Treap *p, int val, int now) {
if(!p) return now;
if(p->val < val)
return Treap_pre(p->R, val, p->val);
return Treap_pre(p->L, val, now);
}
int Treap_suc(Treap *p, int val, int now) {
if(!p) return now;
if(p->val > val) return Treap_suc(p->L, val, p->val);
return Treap_suc(p->R, val, now);
}
int main() {
cin >> n;
while(n--) {
int opt, x;
scanf("%d%d", &opt, &x);
if(opt == 1) Treap_insert(root, x);
else if(opt == 2) Treap_Del(root, x);
else if(opt == 3) printf("%d\n", Treap_Rank(root, x) + 1);
else if(opt == 4) printf("%d\n", Treap_Find(root, x));
else if(opt == 5) printf("%d\n", Treap_pre(root, x, root->val));
else if(opt == 6) printf("%d\n", Treap_suc(root, x, root->val));
}
return 0;
}
|
