library/tree/TreeLazy.hpp
Depends on
Verified with
Code
#pragma once
#include "library/algebra/lazy/Reverse.hpp"
#include "library/segtree/LazySegmentTree.hpp"
#include "library/tree/HLD.hpp"
template <typename TREE, typename Lazy> struct TreeLazy {
using MX = typename Lazy::MX;
using MF = typename Lazy::MF;
using X = typename MX::value_type;
using F = typename MF::value_type;
using Lazy_r = LazyReverse<Lazy>;
int n;
TREE T;
HLD<Tree> hld;
std::vector<int> hld_id, euler_in, euler_out;
LazySegmentTree<Lazy> seg;
LazySegmentTree<Lazy_r> seg_r;
TreeLazy(const TREE &T_, int r = 0)
: T(T_), hld(T_), n(T_.n), seg(n), seg_r(n) {
T.build(r);
hld_id = hld.build(r);
}
TreeLazy(const TREE &T_, std::vector<X> a, int r = 0)
: T(T_), hld(T_), n(T_.n) {
T.build(r);
hld_id = hld.build(r);
std::vector<X> hld_a(n);
for (int v = 0; v < n; v++)
hld_a[hld_id[v]] = a[v];
seg = LazySegmentTree<Lazy>(hld_a);
if (!MX::commute)
seg_r = LazySegmentTree<Lazy_r>(hld_a);
}
void set(int v, X x) {
seg.set(hld_id[v], x);
if (!MX::commute)
seg_r.set(hld_id[v], x);
}
void multiply(int v, X x) {
seg.multiply(hld_id[v], x);
if (!MX::commute)
seg_r.multiply(hld_id[v], x);
}
X get(int v) { return seg.get(hld_id[v]); }
// [u,v]パスの monoid 積
X path_prod(int u, int v) {
auto [path_u, path_v] = hld.path(u, v);
X prod_u = MX::unit(), prod_v = MX::unit();
for (const auto &[l, r] : path_u) {
X val = (MX::commute ? seg.prod(r, l + 1) : seg_r.prod(r, l + 1));
MX::Rchop(prod_u, val);
}
for (const auto &[l, r] : path_v) {
X val = seg.prod(r, l + 1);
MX::Lchop(val, prod_v);
}
return MX::op(prod_u, prod_v);
}
// root -> path
X path_root_prod(int v) { return path_prod(T.root, v); }
void path_apply(int u, int v, const F &f) {
auto [path_u, path_v] = hld.path(u, v);
for (const auto &[l, r] : path_u) {
seg.apply(r, l + 1, f);
if (!MX::commute)
seg_r.apply(r, l + 1, f);
}
for (const auto &[l, r] : path_v) {
seg.apply(r, l + 1, f);
if (!MX::commute)
seg_r.apply(r, l + 1, f);
}
}
void path_root_apply(int v, const F &f) { path_apply(T.root, v, f); }
X subtree_prod(int v) {
assert(MX::commute);
auto [l, r] = hld.subtree(v);
return seg.prod(l, r);
}
void subtree_apply(int v, const F &f) {
auto [l, r] = hld.subtree(v);
seg.apply(l, r, f);
if (!MX::commute)
seg_r.apply(l, r, f);
}
};
#line 2 "library/algebra/Reverse.hpp"
template<typename Algebra>
struct AlgebraReverse:Algebra{
using X=typename Algebra::value_type;
static constexpr X op(const X& x, const X& y){ return Algebra::op(y,x); }
static constexpr void Rchop(X&x,const X&y){ Algebra::Lchop(y,x); }
static constexpr void Lchop(const X&x,X&y){ Algebra::Rchop(y,x); }
};
#line 3 "library/algebra/lazy/Reverse.hpp"
template <typename Lazy> struct LazyReverse : Lazy {
using MX = AlgebraReverse<typename Lazy::MX>;
};
#line 2 "library/segtree/LazySegmentTree.hpp"
template <typename Lazy> class LazySegmentTree {
using MX = typename Lazy::MX;
using MF = typename Lazy::MF;
using X = typename MX::value_type;
using F = typename MF::value_type;
int n, log, size;
std::vector<X> dat;
std::vector<F> laz;
X reflect(int k) {
if (k < size)
return Lazy::mapping(laz[k], dat[k]);
return dat[k];
}
void point_apply(int k, const F &f) {
if (k < size)
MF::Lchop(f, laz[k]);
else
dat[k] = Lazy::mapping(f, dat[k]);
}
void push(int k) {
dat[k] = reflect(k);
point_apply(2 * k, laz[k]);
point_apply(2 * k + 1, laz[k]);
laz[k] = MF::unit();
}
void thrust(int k) {
for (int i = log; i; i--)
push(k >> i);
}
void update(int i) { dat[i] = MX::op(reflect(2 * i), reflect(2 * i + 1)); }
void recalc(int k) {
while (k >>= 1)
update(k);
}
public:
LazySegmentTree() : LazySegmentTree(0) {}
LazySegmentTree(int n) : LazySegmentTree(std::vector<X>(n, MX::unit())) {}
LazySegmentTree(const std::vector<X> &v) : n(v.size()) {
for (log = 1; (1 << log) < n; log++) {
}
size = 1 << log;
dat.assign(size << 1, MX::unit());
laz.assign(size, MF::unit());
for (int i = 0; i < n; ++i)
dat[size + i] = v[i];
for (int i = size - 1; i >= 1; --i)
update(i);
}
void set(int p, X x) {
assert(0 <= p and p < n);
thrust(p += size);
dat[p] = x;
recalc(p);
}
X operator[](int p) {
assert(0 <= p and p < n);
thrust(p += size);
return reflect(p);
}
X prod(int L, int R) {
assert(0 <= L and L <= R and R <= n);
if (L == R)
return MX::unit();
thrust(L += size);
thrust((R += size - 1)++);
X vl = MX::unit(), vr = MX::unit();
while (L < R) {
if (L & 1)
MX::Rchop(vl, reflect(L++));
if (R & 1)
MX::Lchop(reflect(--R), vr);
L >>= 1, R >>= 1;
}
return MX::op(vl, vr);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= n);
if (l == r)
return;
thrust(l += size);
thrust(r += size - 1);
for (int L = l, R = r + 1; L < R; L >>= 1, R >>= 1) {
if (L & 1)
point_apply(L++, f);
if (R & 1)
point_apply(--R, f);
}
recalc(l);
recalc(r);
}
};
#line 2 "library/tree/HLD.hpp"
template <typename TREE> struct HLD {
int n;
TREE T;
std::vector<int> sz, head, id, id2, rev_id;
bool prepared;
HLD(TREE T_)
: T(T_), n(T_.n), sz(n), head(n), id(n), id2(n), rev_id(n), prepared(false) {}
HLD() = default;
private:
void dfs_sz(int v) {
sz[v] = 1;
for (auto &e : T.son(v)) {
dfs_sz(e.to);
sz[v] += sz[e.to];
if (sz[e.to] > sz[T.son(v)[0].to])
std::swap(e, T.son(v)[0]);
}
}
void dfs_hld(int v, int &k) {
id[v] = k++;
rev_id[id[v]] = v;
for (int i = 0; i < T.son(v).size(); i++) {
int to = T.son(v)[i];
head[to] = (i ? to : head[v]);
dfs_hld(to, k);
}
id2[v] = k;
}
public:
std::vector<int> build(int r = 0) {
assert(!prepared);
prepared = true;
if (~T.root)
assert(T.root == r);
else
T.build(r);
head[r] = r;
dfs_sz(r);
int k = 0;
dfs_hld(r, k);
return id;
}
int lca(int u, int v) const {
assert(prepared);
while (head[u] != head[v])
if (T.depth[head[u]] > T.depth[head[v]])
u = T.parent(head[u]);
else
v = T.parent(head[v]);
return (T.depth[u] < T.depth[v] ? u : v);
}
int distance(int u, int v) const {
int w = lca(u, v);
return T.depth[u] + T.depth[v] - T.depth[w] * 2;
}
// v の k 個上の頂点を返す
int kth_parent(int v, int k) const {
assert(prepared);
if(T.depth[v] < k)
return -1;
while(T.depth[v] - T.depth[head[v]] < k){
k -= T.depth[v] - T.depth[head[v]] + 1;
v = T.parent(head[v]);
}
return rev_id[id[v] - k];
}
// u から v へ k 回移動した頂点を返す
int jump(int u, int v, int k) const {
assert(prepared);
int w = lca(u, v);
if(T.depth[u] + T.depth[v] - T.depth[w] * 2 < k)
return -1;
if(T.depth[u] - T.depth[w] >= k)
return kth_parent(u, k);
return kth_parent(v, T.depth[u] + T.depth[v] - T.depth[w] * 2 - k);
}
// l=lca(u,v) とした時、[u,l] パスと [v,l] パス を閉区間の組みで返す
using path_t = std::vector<std::pair<int, int>>;
std::pair<path_t, path_t> path(int u, int v) const {
assert(prepared);
path_t path_u, path_v;
while (u != v) {
if (head[u] == head[v]) {
if (T.depth[u] < T.depth[v])
path_v.emplace_back(id[v], id[u]);
else
path_u.emplace_back(id[u], id[v]);
break;
}
if (T.depth[head[u]] < T.depth[head[v]]) {
path_v.emplace_back(id[v], id[head[v]]);
v = T.parent(head[v]);
} else {
path_u.emplace_back(id[u], id[head[u]]);
u = T.parent(head[u]);
}
}
if (u == v)
path_u.emplace_back(id[u], id[u]);
return {path_u, path_v};
}
// [l,r) が v の部分木
std::pair<int, int> subtree(int v) const {
assert(prepared);
return {id[v], id2[v]};
}
};
#line 5 "library/tree/TreeLazy.hpp"
template <typename TREE, typename Lazy> struct TreeLazy {
using MX = typename Lazy::MX;
using MF = typename Lazy::MF;
using X = typename MX::value_type;
using F = typename MF::value_type;
using Lazy_r = LazyReverse<Lazy>;
int n;
TREE T;
HLD<Tree> hld;
std::vector<int> hld_id, euler_in, euler_out;
LazySegmentTree<Lazy> seg;
LazySegmentTree<Lazy_r> seg_r;
TreeLazy(const TREE &T_, int r = 0)
: T(T_), hld(T_), n(T_.n), seg(n), seg_r(n) {
T.build(r);
hld_id = hld.build(r);
}
TreeLazy(const TREE &T_, std::vector<X> a, int r = 0)
: T(T_), hld(T_), n(T_.n) {
T.build(r);
hld_id = hld.build(r);
std::vector<X> hld_a(n);
for (int v = 0; v < n; v++)
hld_a[hld_id[v]] = a[v];
seg = LazySegmentTree<Lazy>(hld_a);
if (!MX::commute)
seg_r = LazySegmentTree<Lazy_r>(hld_a);
}
void set(int v, X x) {
seg.set(hld_id[v], x);
if (!MX::commute)
seg_r.set(hld_id[v], x);
}
void multiply(int v, X x) {
seg.multiply(hld_id[v], x);
if (!MX::commute)
seg_r.multiply(hld_id[v], x);
}
X get(int v) { return seg.get(hld_id[v]); }
// [u,v]パスの monoid 積
X path_prod(int u, int v) {
auto [path_u, path_v] = hld.path(u, v);
X prod_u = MX::unit(), prod_v = MX::unit();
for (const auto &[l, r] : path_u) {
X val = (MX::commute ? seg.prod(r, l + 1) : seg_r.prod(r, l + 1));
MX::Rchop(prod_u, val);
}
for (const auto &[l, r] : path_v) {
X val = seg.prod(r, l + 1);
MX::Lchop(val, prod_v);
}
return MX::op(prod_u, prod_v);
}
// root -> path
X path_root_prod(int v) { return path_prod(T.root, v); }
void path_apply(int u, int v, const F &f) {
auto [path_u, path_v] = hld.path(u, v);
for (const auto &[l, r] : path_u) {
seg.apply(r, l + 1, f);
if (!MX::commute)
seg_r.apply(r, l + 1, f);
}
for (const auto &[l, r] : path_v) {
seg.apply(r, l + 1, f);
if (!MX::commute)
seg_r.apply(r, l + 1, f);
}
}
void path_root_apply(int v, const F &f) { path_apply(T.root, v, f); }
X subtree_prod(int v) {
assert(MX::commute);
auto [l, r] = hld.subtree(v);
return seg.prod(l, r);
}
void subtree_apply(int v, const F &f) {
auto [l, r] = hld.subtree(v);
seg.apply(l, r, f);
if (!MX::commute)
seg_r.apply(l, r, f);
}
};
Back to top page
build/pch/stdc++.hpp