This documentation is automatically generated by online-judge-tools/verification-helper
#include "datastructure/dynamic_segtree.hpp"set した位置の分だけ作る。dynamic_segtree<M>(lo = -2^62, hi = 2^62): M は S, op, e を static メンバとして持つ構造体。添字 $[\text{lo}, \text{hi})$ の全要素 M::e() の列を作る。set(p, x): a[p] を x にする。get(p): a[p] を返す。prod(l, r): op(a[l], ..., a[r - 1]) を返す。$l = r$ なら e()。all_prod(): op(a[lo], ..., a[hi - 1]) を返す。max_right(l, f): f(op(a[l], ..., a[r - 1])) が真となる最大の r を返す。全体で真なら hi。f は atcoder::segtree と同じ条件を満たすもの。min_left(r, f): f(op(a[l], ..., a[r - 1])) が真となる最小の l を返す。全体で真なら lo。set, get: $\text{lo} \le p < \text{hi}$prod: $\text{lo} \le l \le r \le \text{hi}$max_right, min_left: $\text{lo} \le l, r \le \text{hi}$set, get, prod, max_right, min_left: $\mathcal{O}(\log N)$all_prod: $\mathcal{O}(1)$set した位置の個数に比例する。#pragma once
#include <cassert>
#include <utility>
#include <vector>
#include "algebra/concept.hpp"
template <monoid M> struct dynamic_segtree {
public:
using S = typename M::S;
explicit dynamic_segtree(long long lo = -(1LL << 62), long long hi = 1LL << 62) : lo(lo), hi(hi) {
assert(lo < hi);
}
void set(long long p, S x) {
assert(lo <= p && p < hi);
root = set(root, lo, hi, p, x);
}
S get(long long p) const {
assert(lo <= p && p < hi);
int t = root;
long long a = lo, b = hi;
while (t != -1) {
if (nodes[t].idx == p) return nodes[t].val;
long long c = mid(a, b);
if (p < c) {
t = nodes[t].l, b = c;
} else {
t = nodes[t].r, a = c;
}
}
return M::e();
}
S prod(long long l, long long r) const {
assert(lo <= l && l <= r && r <= hi);
return prod(root, lo, hi, l, r);
}
S all_prod() const {
return root == -1 ? M::e() : nodes[root].prod;
}
template <bool (*f)(S)> long long max_right(long long l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F> long long max_right(long long l, F f) const {
assert(lo <= l && l <= hi);
S product = M::e();
assert(f(product));
return max_right(root, lo, hi, l, f, product);
}
template <bool (*f)(S)> long long min_left(long long r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F> long long min_left(long long r, F f) const {
assert(lo <= r && r <= hi);
S product = M::e();
assert(f(product));
return min_left(root, lo, hi, r, f, product);
}
private:
struct node {
long long idx;
S val, prod;
int l = -1, r = -1;
};
long long lo, hi;
int root = -1;
std::vector<node> nodes;
static long long mid(long long a, long long b) {
return a + (long long)(((unsigned long long)b - (unsigned long long)a) / 2);
}
void update(int t) {
node& v = nodes[t];
S res = v.l == -1 ? v.val : M::op(nodes[v.l].prod, v.val);
v.prod = v.r == -1 ? res : M::op(res, nodes[v.r].prod);
}
int set(int t, long long a, long long b, long long p, S x) {
if (t == -1) {
nodes.push_back({p, x, x});
return int(nodes.size()) - 1;
}
if (nodes[t].idx == p) {
nodes[t].val = x;
update(t);
return t;
}
long long c = mid(a, b);
if (p < c) {
if (nodes[t].idx < p) std::swap(nodes[t].idx, p), std::swap(nodes[t].val, x);
int child = set(nodes[t].l, a, c, p, x);
nodes[t].l = child;
} else {
if (p < nodes[t].idx) std::swap(nodes[t].idx, p), std::swap(nodes[t].val, x);
int child = set(nodes[t].r, c, b, p, x);
nodes[t].r = child;
}
update(t);
return t;
}
S prod(int t, long long a, long long b, long long l, long long r) const {
if (t == -1 || b <= l || r <= a) return M::e();
const node& v = nodes[t];
if (l <= a && b <= r) return v.prod;
long long c = mid(a, b);
S res = prod(v.l, a, c, l, r);
if (l <= v.idx && v.idx < r) res = M::op(res, v.val);
return M::op(res, prod(v.r, c, b, l, r));
}
template <class F>
long long max_right(int t, long long a, long long b, long long l, const F& f, S& product) const {
if (t == -1 || b <= l) return hi;
const node& v = nodes[t];
if (l <= a && f(M::op(product, v.prod))) {
product = M::op(product, v.prod);
return hi;
}
long long c = mid(a, b);
long long res = max_right(v.l, a, c, l, f, product);
if (res != hi) return res;
if (l <= v.idx) {
product = M::op(product, v.val);
if (!f(product)) return v.idx;
}
return max_right(v.r, c, b, l, f, product);
}
template <class F>
long long min_left(int t, long long a, long long b, long long r, const F& f, S& product) const {
if (t == -1 || r <= a) return lo;
const node& v = nodes[t];
if (b <= r && f(M::op(v.prod, product))) {
product = M::op(v.prod, product);
return lo;
}
long long c = mid(a, b);
long long res = min_left(v.r, c, b, r, f, product);
if (res != lo) return res;
if (v.idx < r) {
product = M::op(v.val, product);
if (!f(product)) return v.idx + 1;
}
return min_left(v.l, a, c, r, f, product);
}
};#line 2 "datastructure/dynamic_segtree.hpp"
#include <cassert>
#include <utility>
#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 7 "datastructure/dynamic_segtree.hpp"
template <monoid M> struct dynamic_segtree {
public:
using S = typename M::S;
explicit dynamic_segtree(long long lo = -(1LL << 62), long long hi = 1LL << 62) : lo(lo), hi(hi) {
assert(lo < hi);
}
void set(long long p, S x) {
assert(lo <= p && p < hi);
root = set(root, lo, hi, p, x);
}
S get(long long p) const {
assert(lo <= p && p < hi);
int t = root;
long long a = lo, b = hi;
while (t != -1) {
if (nodes[t].idx == p) return nodes[t].val;
long long c = mid(a, b);
if (p < c) {
t = nodes[t].l, b = c;
} else {
t = nodes[t].r, a = c;
}
}
return M::e();
}
S prod(long long l, long long r) const {
assert(lo <= l && l <= r && r <= hi);
return prod(root, lo, hi, l, r);
}
S all_prod() const {
return root == -1 ? M::e() : nodes[root].prod;
}
template <bool (*f)(S)> long long max_right(long long l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F> long long max_right(long long l, F f) const {
assert(lo <= l && l <= hi);
S product = M::e();
assert(f(product));
return max_right(root, lo, hi, l, f, product);
}
template <bool (*f)(S)> long long min_left(long long r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F> long long min_left(long long r, F f) const {
assert(lo <= r && r <= hi);
S product = M::e();
assert(f(product));
return min_left(root, lo, hi, r, f, product);
}
private:
struct node {
long long idx;
S val, prod;
int l = -1, r = -1;
};
long long lo, hi;
int root = -1;
std::vector<node> nodes;
static long long mid(long long a, long long b) {
return a + (long long)(((unsigned long long)b - (unsigned long long)a) / 2);
}
void update(int t) {
node& v = nodes[t];
S res = v.l == -1 ? v.val : M::op(nodes[v.l].prod, v.val);
v.prod = v.r == -1 ? res : M::op(res, nodes[v.r].prod);
}
int set(int t, long long a, long long b, long long p, S x) {
if (t == -1) {
nodes.push_back({p, x, x});
return int(nodes.size()) - 1;
}
if (nodes[t].idx == p) {
nodes[t].val = x;
update(t);
return t;
}
long long c = mid(a, b);
if (p < c) {
if (nodes[t].idx < p) std::swap(nodes[t].idx, p), std::swap(nodes[t].val, x);
int child = set(nodes[t].l, a, c, p, x);
nodes[t].l = child;
} else {
if (p < nodes[t].idx) std::swap(nodes[t].idx, p), std::swap(nodes[t].val, x);
int child = set(nodes[t].r, c, b, p, x);
nodes[t].r = child;
}
update(t);
return t;
}
S prod(int t, long long a, long long b, long long l, long long r) const {
if (t == -1 || b <= l || r <= a) return M::e();
const node& v = nodes[t];
if (l <= a && b <= r) return v.prod;
long long c = mid(a, b);
S res = prod(v.l, a, c, l, r);
if (l <= v.idx && v.idx < r) res = M::op(res, v.val);
return M::op(res, prod(v.r, c, b, l, r));
}
template <class F>
long long max_right(int t, long long a, long long b, long long l, const F& f, S& product) const {
if (t == -1 || b <= l) return hi;
const node& v = nodes[t];
if (l <= a && f(M::op(product, v.prod))) {
product = M::op(product, v.prod);
return hi;
}
long long c = mid(a, b);
long long res = max_right(v.l, a, c, l, f, product);
if (res != hi) return res;
if (l <= v.idx) {
product = M::op(product, v.val);
if (!f(product)) return v.idx;
}
return max_right(v.r, c, b, l, f, product);
}
template <class F>
long long min_left(int t, long long a, long long b, long long r, const F& f, S& product) const {
if (t == -1 || r <= a) return lo;
const node& v = nodes[t];
if (b <= r && f(M::op(v.prod, product))) {
product = M::op(v.prod, product);
return lo;
}
long long c = mid(a, b);
long long res = min_left(v.r, c, b, r, f, product);
if (res != lo) return res;
if (v.idx < r) {
product = M::op(v.val, product);
if (!f(product)) return v.idx + 1;
}
return min_left(v.l, a, c, r, f, product);
}
};