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
|
#include "free_queue.h"
#include <cassert>
#include <vector>
template <typename NodeBase, typename Impl> struct AVLTreeBase {
struct Node : public NodeBase {
int height;
size_t size;
Node *left, *right;
};
explicit AVLTreeBase(int n_) : nodes(n_ << 1), free_queue(n_ << 1) {
assert(free_queue.allocate() == 0);
auto n = null_node();
n->height = 0;
n->size = 0;
n->left = n->right = null_node();
}
Node *null_node() { return nodes.data(); }
Node *new_leaf() {
auto n = new_node();
n->height = 0;
n->size = 1;
n->left = n->right = null_node();
return n;
}
Node *merge(Node *u, Node *v) {
if (u == null_node()) {
return v;
}
if (v == null_node()) {
return u;
}
if (std::abs(u->height - v->height) <= 1) {
return new_node(u, v);
}
Impl::propagate(v);
if (u->height + 2 == v->height && v->right->height + 2 == v->height) {
auto [vl, vr] = destruct(v);
auto [vll, vlr] = destruct(vl);
return new_node(new_node(u, vll), new_node(vlr, vr));
}
if (u->height < v->height) {
auto [vl, vr] = destruct(v);
return merge(merge(u, vl), vr);
} else {
auto [ul, ur] = destruct(u);
return merge(ul, merge(ur, v));
}
}
std::pair<Node *, Node *> split(Node *u, size_t k) {
if (k == 0) {
return {null_node(), u};
}
if (k == u->size) {
return {u, null_node()};
}
auto [ul, ur] = destruct(u);
if (k <= ul->size) {
auto [a, b] = split(ul, k);
return {a, merge(b, ur)};
} else {
auto [a, b] = split(ur, k - ul->size);
return {merge(ul, a), b};
}
}
private:
Node *collect(Node *n) {
n->height = std::max(n->left->height, n->right->height) + 1;
n->size = n->left->size + n->right->size;
Impl::collect(n);
return n;
}
Node *new_node() { return new (nodes.data() + free_queue.allocate()) Node(); }
Node *new_node(Node *l, Node *r) {
auto n = new_node();
n->left = l;
n->right = r;
return collect(n);
}
std::pair<Node *, Node *> destruct(Node *u) {
Impl::propagate(u);
free_node(u);
return {u->left, u->right};
}
void free_node(Node *n) { free_queue.free(n - nodes.data()); }
std::vector<Node> nodes;
FreeQueue free_queue;
};
|
