/
splaytree_acted_set.hpp
72 lines (65 loc) · 1.52 KB
/
splaytree_acted_set.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
61
62
63
64
65
66
67
68
69
70
71
72
#include "ds/splaytree/splaytree.hpp"
namespace SplayTreeNodes {
template <typename ActedSet>
struct Node_AS {
using Monoid_A = typename ActedSet::Monoid_A;
using A = typename ActedSet::A;
using S = typename ActedSet::S;
using value_type = S;
using operator_type = A;
using np = Node_AS *;
np p, l, r;
S x;
A lazy;
u32 size;
bool rev;
static void new_node(np n, const S &x) {
n->p = n->l = n->r = nullptr;
n->x = x;
n->lazy = Monoid_A::unit();
n->size = 1;
n->rev = 0;
}
void update() {
size = 1;
if (l) { size += l->size; }
if (r) { size += r->size; }
}
void prop() {
if (lazy != Monoid_A::unit()) {
if (l) { l->apply(lazy); }
if (r) { r->apply(lazy); }
lazy = Monoid_A::unit();
}
if (rev) {
if (l) {
l->rev ^= 1;
swap(l->l, l->r);
}
if (r) {
r->rev ^= 1;
swap(r->l, r->r);
}
rev = 0;
}
}
// update, prop 以外で呼ばれるものは、splay 後であることが想定されている。
// したがってその時点で update, prop 済であることを仮定してよい。
S get() { return x; }
void set(const S &xx) {
x = xx;
update();
}
void apply(const A &a) {
x = ActedSet::act(x, a);
lazy = Monoid_A::op(lazy, a);
}
void reverse() {
swap(l, r);
rev ^= 1;
}
};
template <typename ActedSet, int NODES>
using SplayTree_ActedSet = SplayTree<Node_AS<ActedSet>, NODES>;
} // namespace SplayTreeNodes
using SplayTreeNodes::SplayTree_ActedSet;