今天我刷题了吗
搜索文档…
树堆
Treap
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int maxn(1e5 + 10);
7
const int inf(0x3f3f3f3f);
8
int idx, root;
9
10
struct node {
11
int l, r;
12
int key, val;
13
int cnt, siz;
14
} tree[maxn];
15
16
template<typename T = int>
17
inline const T read()
18
{
19
T x = 0, f = 1;
20
char ch = getchar();
21
while (ch < '0' || ch > '9') {
22
if (ch == '-') f = -1;
23
ch = getchar();
24
}
25
while (ch >= '0' && ch <= '9') {
26
x = (x << 3) + (x << 1) + ch - '0';
27
ch = getchar();
28
}
29
return x * f;
30
}
31
32
template<typename T>
33
inline void write(T x, bool ln)
34
{
35
if (x < 0) {
36
putchar('-');
37
x = -x;
38
}
39
if (x > 9) write(x / 10, false);
40
putchar(x % 10 + '0');
41
if (ln) putchar(10);
42
}
43
44
inline int new_node(int key)
45
{
46
++idx;
47
tree[idx].key = key;
48
tree[idx].val = rand();
49
tree[idx].cnt = tree[idx].siz = 1;
50
return idx;
51
}
52
53
inline void push_up(int cur)
54
{
55
tree[cur].siz = tree[tree[cur].l].siz + tree[tree[cur].r].siz + tree[cur].cnt;
56
}
57
58
inline void zig(int& cur)
59
{
60
int ls = tree[cur].l;
61
tree[cur].l = tree[ls].r;
62
tree[ls].r = cur;
63
cur = ls;
64
push_up(tree[cur].r);
65
push_up(cur);
66
}
67
68
inline void zag(int& cur)
69
{
70
int rs = tree[cur].r;
71
tree[cur].r = tree[rs].l;
72
tree[rs].l = cur;
73
cur = rs;
74
push_up(tree[cur].l);
75
push_up(cur);
76
}
77
78
void build()
79
{
80
root = new_node(-inf);
81
tree[root].r = new_node(inf);
82
push_up(root);
83
if (tree[root].val < tree[tree[root].r].val) {
84
zag(root);
85
}
86
}
87
88
inline void insert(int& cur, int key)
89
{
90
if (not cur) {
91
cur = new_node(key);
92
} else if (key == tree[cur].key) {
93
++tree[cur].cnt;
94
} else if (key < tree[cur].key) {
95
insert(tree[cur].l, key);
96
if (tree[tree[cur].l].val > tree[cur].val) {
97
zig(cur);
98
}
99
} else {
100
insert(tree[cur].r, key);
101
if (tree[tree[cur].r].val > tree[cur].val) {
102
zag(cur);
103
}
104
}
105
push_up(cur);
106
}
107
108
inline void remove(int& cur, int key)
109
{
110
if (not cur) return;
111
if (key == tree[cur].key) {
112
if (tree[cur].cnt > 1) {
113
--tree[cur].cnt;
114
} else if (tree[cur].l or tree[cur].r) {
115
if (not tree[cur].r or tree[tree[cur].l].val > tree[tree[cur].r].val) {
116
zig(cur);
117
remove(tree[cur].r, key);
118
} else {
119
zag(cur);
120
remove(tree[cur].l, key);
121
}
122
} else {
123
cur = 0;
124
}
125
} else if (key < tree[cur].key) {
126
remove(tree[cur].l, key);
127
} else {
128
remove(tree[cur].r, key);
129
}
130
push_up(cur);
131
}
132
133
inline int get_rank(int cur, int key)
134
{
135
if (not cur) {
136
return 0;
137
}
138
if (key == tree[cur].key) {
139
return tree[tree[cur].l].siz + 1;
140
}
141
if (key < tree[cur].key) {
142
return get_rank(tree[cur].l, key);
143
}
144
return get_rank(tree[cur].r, key) + tree[tree[cur].l].siz + tree[cur].cnt;
145
}
146
147
inline int get_key(int cur, int rank)
148
{
149
if (not cur) {
150
return inf;
151
}
152
if (rank <= tree[tree[cur].l].siz) {
153
return get_key(tree[cur].l, rank);
154
}
155
if (rank <= tree[tree[cur].l].siz + tree[cur].cnt) {
156
return tree[cur].key;
157
}
158
return get_key(tree[cur].r, rank - tree[cur].cnt - tree[tree[cur].l].siz);
159
}
160
161
inline int get_prev(int cur, int key)
162
{
163
if (not cur) {
164
return -inf;
165
}
166
if (key <= tree[cur].key) {
167
return get_prev(tree[cur].l, key);
168
}
169
return max(tree[cur].key, get_prev(tree[cur].r, key));
170
}
171
172
inline int get_next(int cur, int key)
173
{
174
if (not cur) {
175
return inf;
176
}
177
if (key >= tree[cur].key) {
178
return get_next(tree[cur].r, key);
179
}
180
return min(tree[cur].key, get_next(tree[cur].l, key));
181
}
182
183
int main()
184
{
185
#ifdef ONLINE_JUDGE
186
#else
187
freopen("input.txt", "r", stdin);
188
#endif
189
build();
190
int n = read();
191
while (n--) {
192
int op = read(), x = read();
193
if (op == 1) {
194
insert(root, x);
195
} else if (op == 2) {
196
remove(root, x);
197
} else if (op == 3) {
198
write(get_rank(root, x) - 1, true);
199
} else if (op == 4) {
200
write(get_key(root, x + 1), true);
201
} else if (op == 5) {
202
write(get_prev(root, x), true);
203
} else {
204
write(get_next(root, x), true);
205
}
206
}
207
return 0;
208
}
Copied!
最近更新 1yr ago
复制链接