lazy link cut tree¶
ソースコード¶
1#include <vector>
2#include <cassert>
3using namespace std;
4
5// LazyLinkCutTree
6namespace titan23 {
7
8 template <class T,
9 class F,
10 T (*op)(T, T),
11 T (*mapping)(F, T),
12 F (*composition)(F, F),
13 T (*e)(),
14 F (*id)()>
15 class LazyLinkCutTree {
16 private:
17 struct Node;
18 using NodePtr = Node*;
19 vector<NodePtr> pool;
20
21 struct Node {
22 int index, size, rev;
23 T key, data, rdata;
24 F lazy;
25 NodePtr left, right, par;
26
27 Node(const int index, const T key, const F lazy) :
28 index(index), size(1), rev(0),
29 key(key), data(key), rdata(key),
30 lazy(lazy),
31 left(nullptr), right(nullptr), par(nullptr) {
32 }
33
34 bool is_root() const {
35 return (!par) || (!(par->left == this || par->right == this));
36 }
37 };
38
39 void _apply_rev(const NodePtr node) {
40 if (!node) return;
41 node->rev ^= 1;
42 }
43
44 void _apply_f(const NodePtr node, const F f) {
45 if (!node) return;
46 node->key = mapping(f, node->key);
47 node->data = mapping(f, node->data);
48 node->rdata = mapping(f, node->rdata);
49 node->lazy = composition(f, node->lazy);
50 }
51
52 void _propagate(const NodePtr node) {
53 if (!node) return;
54 if (node->rev) {
55 swap(node->data, node->rdata);
56 swap(node->left, node->right);
57 _apply_rev(node->left);
58 _apply_rev(node->right);
59 node->rev = 0;
60 }
61 if (node->lazy != id()) {
62 _apply_f(node->left, node->lazy);
63 _apply_f(node->right, node->lazy);
64 node->lazy = id();
65 }
66 }
67
68 void _update(const NodePtr node) {
69 if (!node) return;
70 _propagate(node->left);
71 _propagate(node->right);
72 node->data = node->key;
73 node->rdata = node->key;
74 node->size = 1;
75 if (node->left) {
76 node->data = op(node->left->data, node->data);
77 node->rdata = op(node->rdata, node->left->rdata);
78 node->size += node->left->size;
79 }
80 if (node->right) {
81 node->data = op(node->data, node->right->data);
82 node->rdata = op(node->right->rdata, node->rdata);
83 node->size += node->right->size;
84 }
85 }
86
87 void _rotate(const NodePtr node) {
88 const NodePtr pnode = node->par;
89 const NodePtr gnode = pnode->par;
90 _propagate(pnode);
91 _propagate(node);
92 if (gnode) {
93 if (gnode->left == pnode) {
94 gnode->left = node;
95 } else if (gnode->right == pnode) {
96 gnode->right = node;
97 }
98 }
99 node->par = gnode;
100 if (pnode->left == node) {
101 pnode->left = node->right;
102 if (node->right) node->right->par = pnode;
103 node->right = pnode;
104 } else {
105 pnode->right = node->left;
106 if (node->left) node->left->par = pnode;
107 node->left = pnode;
108 }
109 pnode->par = node;
110 _update(pnode);
111 _update(node);
112 }
113
114 void _splay(const NodePtr node) {
115 while ((!node->is_root()) && (!node->par->is_root())) {
116 if ((node->par->par->left == node->par) == (node->par->left == node)) {
117 _rotate(node->par);
118 } else {
119 _rotate(node);
120 }
121 _rotate(node);
122 }
123 if (!node->is_root()) _rotate(node);
124 _propagate(node);
125 }
126
127 void _link(const NodePtr c, const NodePtr p) {
128 _expose(c);
129 _expose(p);
130 c->par = p;
131 p->right = c;
132 _update(p);
133 }
134
135 void _cut(const NodePtr c) {
136 _expose(c);
137 c->left->par = nullptr;
138 c->left = nullptr;
139 _update(c);
140 }
141
142 NodePtr _expose(const NodePtr node) {
143 NodePtr pre = node;
144 while (node->par) {
145 _splay(node);
146 node->right = nullptr;
147 _update(node);
148 if (!node->par) break;
149 pre = node->par;
150 _splay(node->par);
151 node->par->right = node;
152 _update(node->par);
153 }
154 node->right = nullptr;
155 _update(node);
156 return pre;
157 }
158
159 NodePtr _root(NodePtr v) {
160 _expose(v);
161 _propagate(v);
162 while (v->left) {
163 v = v->left;
164 _propagate(v);
165 }
166 _splay(v);
167 return v;
168 }
169
170 void _evert(NodePtr v) {
171 _expose(v);
172 _apply_rev(v);
173 _propagate(v);
174 }
175
176 public:
177 LazyLinkCutTree() {}
178
179 LazyLinkCutTree(int n) {
180 pool.resize(n);
181 for (int i = 0; i < n; ++i) {
182 pool[i] = new Node(i, e(), id());
183 }
184 }
185
186 int expose(int v) {
187 return _expose(pool[v])->index;
188 }
189
190 int lca(int u, int v, int root=-1) {
191 if (root != -1) evert(root);
192 expose(u);
193 return expose(v);
194 }
195
196 void link(int c, int p) {
197 _link(pool[c], pool[p]);
198 }
199
200 void cut(int c) {
201 _cut(pool[c]);
202 }
203
204 int root(int v) {
205 return _root(pool[v])->index;
206 }
207
208 bool same(int u, int v) {
209 return root(u) == root(v);
210 }
211
212 void evert(int v) {
213 _evert(pool[v]);
214 }
215
216 T path_prod(int u, int v) {
217 evert(u);
218 expose(v);
219 return pool[v]->data;
220 }
221
222 void path_apply(int u, int v, F f) {
223 evert(u);
224 expose(v);
225 _apply_f(pool[v], f);
226 _propagate(pool[v]);
227 }
228
229 bool merge(int u, int v) {
230 if (same(u, v)) return false;
231 evert(u);
232 link(u, v);
233 return true;
234 }
235
236 void split(int u, int v) {
237 evert(u);
238 cut(v);
239 }
240
241 T get(int k) {
242 _splay(pool[k]);
243 return pool[k]->key;
244 }
245
246 void set(int k, T v) {
247 NodePtr node = pool[k];
248 _splay(node);
249 node->key = v;
250 _update(node);
251 }
252
253 int path_kth_elm(int s, int t, int k) {
254 evert(s);
255 expose(t);
256 NodePtr node = pool[t];
257 if (node->size <= k) return -1;
258 while (true) {
259 _propagate(node);
260 t = node->left? node->left->size: 0;
261 if (t == k) {
262 _splay(node);
263 return node->index;
264 }
265 if (t > k) {
266 node = node->left;
267 } else {
268 node = node->right;
269 k -= t + 1;
270 }
271 }
272 }
273 };
274} // namespace titan23
仕様¶
Warning
doxygenfile: Cannot find file “titan_cpplib/data_structures/lazy_link_cut_tree.cpp