This documentation is automatically generated by online-judge-tools/verification-helper
#include "datastructure/persistent_segtree.hpp"int の番号で扱う。persistent_segtree<M>(n): M は S, op, e を static メンバとして持つ構造体。全要素 M::e() の長さ $n$ の列を版 $0$ として作る。persistent_segtree<M>(v): 列 v を版 $0$ として作る。size(): 列の長さを返す。get(root, p): 版 root の a[p] を返す。set(root, p, x): 版 root の a[p] を x に変えた新しい版を作り、その番号を返す。版 root は変わらない。prod(root, l, r): 版 root の op(a[l], ..., a[r - 1]) を返す。$l = r$ なら e()。all_prod(root): 版 root の op(a[0], ..., a[n - 1]) を返す。get, set, prod: $\mathcal{O}(\log n)$。set 1 回でメモリが $\mathcal{O}(\log n)$ 増える。all_prod: $\mathcal{O}(1)$#pragma once
#include <cassert>
#include <vector>
#include "algebra/concept.hpp"
template <monoid M> struct persistent_segtree {
public:
using S = typename M::S;
explicit persistent_segtree(int n) : persistent_segtree(std::vector<S>(n, M::e())) {
}
explicit persistent_segtree(const std::vector<S>& v) : _n(int(v.size())) {
nodes.reserve(2 * _n);
if (_n > 0) build(v, 0, _n);
}
int size() const {
return _n;
}
S get(int root, int p) const {
assert(0 <= p && p < _n);
int cur = root, l = 0, r = _n;
while (r - l > 1) {
int mid = (l + r) / 2;
if (p < mid) {
cur = nodes[cur].l, r = mid;
} else {
cur = nodes[cur].r, l = mid;
}
}
return nodes[cur].val;
}
int set(int root, int p, const S& x) {
assert(0 <= p && p < _n);
int res = copy(root);
int cur = res, l = 0, r = _n;
path.clear();
while (r - l > 1) {
path.push_back(cur);
int mid = (l + r) / 2;
if (p < mid) {
int nxt = copy(nodes[cur].l);
nodes[cur].l = nxt;
cur = nxt, r = mid;
} else {
int nxt = copy(nodes[cur].r);
nodes[cur].r = nxt;
cur = nxt, l = mid;
}
}
nodes[cur].val = x;
for (int i = int(path.size()) - 1; i >= 0; i--) {
node& v = nodes[path[i]];
v.val = M::op(nodes[v.l].val, nodes[v.r].val);
}
return res;
}
S prod(int root, int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
return prod(root, 0, _n, l, r);
}
S all_prod(int root) const {
return _n == 0 ? M::e() : nodes[root].val;
}
private:
struct node {
int l, r;
S val;
};
int _n;
std::vector<node> nodes;
std::vector<int> path;
int copy(int v) {
nodes.push_back(nodes[v]);
return int(nodes.size()) - 1;
}
int build(const std::vector<S>& v, int l, int r) {
if (r - l == 1) {
nodes.push_back({-1, -1, v[l]});
return int(nodes.size()) - 1;
}
int mid = (l + r) / 2;
int res = int(nodes.size());
nodes.push_back({-1, -1, M::e()});
int lc = build(v, l, mid);
int rc = build(v, mid, r);
nodes[res].l = lc, nodes[res].r = rc;
nodes[res].val = M::op(nodes[lc].val, nodes[rc].val);
return res;
}
S prod(int cur, int nl, int nr, int l, int r) const {
if (r <= nl || nr <= l) return M::e();
if (l <= nl && nr <= r) return nodes[cur].val;
int mid = (nl + nr) / 2;
return M::op(prod(nodes[cur].l, nl, mid, l, r), prod(nodes[cur].r, mid, nr, l, r));
}
};#line 2 "datastructure/persistent_segtree.hpp"
#include <cassert>
#include <vector>
#line 2 "algebra/concept.hpp"
#include <concepts>
template <class M>
concept semigroup = requires(typename M::S a, typename M::S b) {
{ M::op(a, b) } -> std::same_as<typename M::S>;
};
template <class M>
concept monoid = semigroup<M> && requires {
{ M::e() } -> std::same_as<typename M::S>;
};
template <class G>
concept group = monoid<G> && requires(typename G::S a) {
{ G::inv(a) } -> std::same_as<typename G::S>;
};
template <class A>
concept action = requires(typename A::F f, typename A::F g) {
{ A::composition(f, g) } -> std::same_as<typename A::F>;
{ A::id() } -> std::same_as<typename A::F>;
{ A::composition_commutative } -> std::convertible_to<bool>;
};
template <class A>
concept acted_monoid = monoid<A> && action<A> && requires(typename A::S x, typename A::F f) {
{ A::mapping(f, x) } -> std::same_as<typename A::S>;
};
template <class R>
concept semiring = requires(typename R::S a, typename R::S b) {
{ R::add(a, b) } -> std::same_as<typename R::S>;
{ R::zero() } -> std::same_as<typename R::S>;
{ R::mul(a, b) } -> std::same_as<typename R::S>;
{ R::one() } -> std::same_as<typename R::S>;
};
template <class A>
concept beats_acted_monoid = acted_monoid<A> && requires(typename A::S x) {
{ x.fail } -> std::convertible_to<bool>;
};
#line 6 "datastructure/persistent_segtree.hpp"
template <monoid M> struct persistent_segtree {
public:
using S = typename M::S;
explicit persistent_segtree(int n) : persistent_segtree(std::vector<S>(n, M::e())) {
}
explicit persistent_segtree(const std::vector<S>& v) : _n(int(v.size())) {
nodes.reserve(2 * _n);
if (_n > 0) build(v, 0, _n);
}
int size() const {
return _n;
}
S get(int root, int p) const {
assert(0 <= p && p < _n);
int cur = root, l = 0, r = _n;
while (r - l > 1) {
int mid = (l + r) / 2;
if (p < mid) {
cur = nodes[cur].l, r = mid;
} else {
cur = nodes[cur].r, l = mid;
}
}
return nodes[cur].val;
}
int set(int root, int p, const S& x) {
assert(0 <= p && p < _n);
int res = copy(root);
int cur = res, l = 0, r = _n;
path.clear();
while (r - l > 1) {
path.push_back(cur);
int mid = (l + r) / 2;
if (p < mid) {
int nxt = copy(nodes[cur].l);
nodes[cur].l = nxt;
cur = nxt, r = mid;
} else {
int nxt = copy(nodes[cur].r);
nodes[cur].r = nxt;
cur = nxt, l = mid;
}
}
nodes[cur].val = x;
for (int i = int(path.size()) - 1; i >= 0; i--) {
node& v = nodes[path[i]];
v.val = M::op(nodes[v.l].val, nodes[v.r].val);
}
return res;
}
S prod(int root, int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
return prod(root, 0, _n, l, r);
}
S all_prod(int root) const {
return _n == 0 ? M::e() : nodes[root].val;
}
private:
struct node {
int l, r;
S val;
};
int _n;
std::vector<node> nodes;
std::vector<int> path;
int copy(int v) {
nodes.push_back(nodes[v]);
return int(nodes.size()) - 1;
}
int build(const std::vector<S>& v, int l, int r) {
if (r - l == 1) {
nodes.push_back({-1, -1, v[l]});
return int(nodes.size()) - 1;
}
int mid = (l + r) / 2;
int res = int(nodes.size());
nodes.push_back({-1, -1, M::e()});
int lc = build(v, l, mid);
int rc = build(v, mid, r);
nodes[res].l = lc, nodes[res].r = rc;
nodes[res].val = M::op(nodes[lc].val, nodes[rc].val);
return res;
}
S prod(int cur, int nl, int nr, int l, int r) const {
if (r <= nl || nr <= l) return M::e();
if (l <= nl && nr <= r) return nodes[cur].val;
int mid = (nl + nr) / 2;
return M::op(prod(nodes[cur].l, nl, mid, l, r), prod(nodes[cur].r, mid, nr, l, r));
}
};