hld lazy segment tree

ソースコード

 1#include <vector>
 2#include "titan_cpplib/graph/hld.cpp"
 3#include "titan_cpplib/others/print.cpp"
 4#include "titan_cpplib/data_structures/lazy_segment_tree.cpp"
 5using namespace std;
 6
 7namespace titan23 {
 8
 9    template <class T,
10            T (*op)(T, T),
11            T (*e)(),
12            class F,
13            T (*mapping)(F, T),
14            F (*composition)(F, F),
15            F (*id)()>
16    class HLDLazySegmentTree {
17      private:
18        titan23::HLD hld;
19        titan23::LazySegmentTree<T, op, e, F, mapping, composition, id> seg, rseg;
20
21      public:
22        HLDLazySegmentTree() {}
23
24        HLDLazySegmentTree(titan23::HLD &hld, int n) : hld(hld) {
25            this->seg = titan23::LazySegmentTree<T, op, e, F, mapping, composition, id>(n);
26            this->rseg = titan23::LazySegmentTree<T, op, e, F, mapping, composition, id>(n);
27        }
28
29        HLDLazySegmentTree(titan23::HLD &hld, vector<T> a) : hld(hld) {
30            vector<T> b = hld.build_list(a);
31            this->seg = titan23::LazySegmentTree<T, op, e, F, mapping, composition, id>(hld.build_list(b));
32            reverse(b.begin(), b.end());
33            this->rseg = titan23::LazySegmentTree<T, op, e, F, mapping, composition, id>(hld.build_list(b));
34        }
35
36        T path_prod(int u, int v) {
37            T lres = e(), rres = e();
38            while (hld.head[u] != hld.head[v]) {
39                if (hld.dep[hld.head[u]] > hld.dep[hld.head[v]]) {
40                    lres = op(lres, rseg.prod(hld.n - hld.nodein[u] - 1, hld.n - hld.nodein[hld.head[u]]));
41                    u = hld.par[hld.head[u]];
42                } else {
43                    rres = op(seg.prod(hld.nodein[hld.head[v]], hld.nodein[v] + 1), rres);
44                    v = hld.par[hld.head[v]];
45                }
46            }
47            if (hld.dep[u] > hld.dep[v]) {
48                lres = op(lres, rseg.prod(hld.n - hld.nodein[u] - 1, hld.n - hld.nodein[v]));
49            } else {
50                lres = op(lres, seg.prod(hld.nodein[u], hld.nodein[v] + 1));
51            }
52            return op(lres, rres);
53        }
54
55        void path_apply(int u, int v, F f) {
56            while (hld.head[u] != hld.head[v]) {
57                if (hld.dep[hld.head[u]] < hld.dep[hld.head[v]]) swap(u, v);
58                seg.apply(hld.nodein[hld.head[u]], hld.nodein[u] + 1, f);
59                rseg.apply(hld.n - (hld.nodein[u] + 1 - 1) - 1, hld.n - hld.nodein[hld.head[u]] - 1 + 1, f);
60                u = hld.par[hld.head[u]];
61            }
62            if (hld.dep[u] < hld.dep[v]) swap(u, v);
63            seg.apply(hld.nodein[v], hld.nodein[u] + 1, f);
64            rseg.apply(hld.n - (hld.nodein[u] + 1 - 1) - 1, hld.n - hld.nodein[v] - 1 + 1, f);
65        }
66
67        T get(int k) {
68            return seg.get(hld.nodein[k]);
69        }
70
71        void set(int k, T v) {
72            seg.set(hld.nodein[k], v);
73            rseg.set(hld.n - hld.nodein[k] - 1, v);
74        }
75
76        T subtree_prod(int v) {
77            return seg.prod(hld.nodein[v], hld.nodeout[v]);
78        }
79
80        void subtree_apply(int v, F f) {
81            seg.apply(hld.nodein[v], hld.nodeout[v], f);
82            rseg.apply(hld.n-hld.nodeout[v]-1-1, hld.n-hld.nodein[v]-1+1, f);
83        }
84    };
85} // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/graph/hld_lazy_segment_tree.cpp