/
meldable_heap.hpp
60 lines (57 loc) · 1.51 KB
/
meldable_heap.hpp
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
template <typename VAL, bool PERSISTENT, int NODES, bool TOP_IS_MIN>
struct Meldable_Heap {
struct Node {
Node *l, *r;
VAL x;
u32 size, dist; // dist: leaf までの距離
};
Node *pool;
int pid;
using np = Node *;
Meldable_Heap() : pid(0) { pool = new Node[NODES]; }
np new_root() { return nullptr; }
np new_node(const VAL &x) {
pool[pid].l = pool[pid].r = nullptr;
pool[pid].x = x, pool[pid].size = 1, pool[pid].dist = 1;
return &(pool[pid++]);
}
np copy_node(np a) {
if (!a || !PERSISTENT) return a;
np b = new_node(a->x);
b->l = a->l, b->r = a->r;
b->size = a->size, b->dist = a->dist;
return b;
}
np meld(np a, np b) {
if (!a) return b;
if (!b) return a;
a = copy_node(a);
b = copy_node(b);
if constexpr (TOP_IS_MIN) {
if ((a->x) > (b->x)) swap(a, b);
} else {
if ((a->x) < (b->x)) swap(a, b);
}
a->r = meld(a->r, b);
if (!(a->l) || (a->l->dist < a->r->dist)) swap(a->l, a->r);
a->dist = (a->r ? a->r->dist : 0) + 1;
a->size = 1;
if (a->l) a->size += a->l->size;
if (a->r) a->size += a->r->size;
return a;
}
np push(np a, VAL x) { return meld(a, new_node(x)); }
np pop(np a) { return meld(a->l, a->r); }
VAL top(np a) { return a->x; }
vc<VAL> get_all(np a) {
vc<VAL> A;
auto dfs = [&](auto &dfs, np a) -> void {
if (!a) return;
A.eb(a->x), dfs(dfs, a->l), dfs(dfs, a->r);
};
dfs(dfs, a);
sort(all(A));
if (!TOP_IS_MIN) reverse(all(A));
return A;
}
};