This documentation is automatically generated by online-judge-tools/verification-helper
#include "src/data-structure/segment-tree/presets/range-chmin-query-solver.hpp"
数列に対する区間chminクエリを処理するデータ構造。
内部ではセグメント木を用いているため、詳細な仕様などはそちらのドキュメントに追従する。
(1) RangeChminQuerySolver< T >(usize n)
(2) RangeChminQuerySolver< T >(usize n, T v)
(3) RangeChminQuerySolver< T >(std::vector< T > vs)
#pragma once
#include "src/data-structure/segment-tree/presets/monoid/operator-structure-chmin.hpp"
#include "src/data-structure/segment-tree/range-mapping-point-fold-segment-tree.hpp"
namespace luz {
template < typename T >
using RangeChminQuerySolver =
DualSegmentTree< monoid::RangeChminQueryMonoid< T > >;
} // namespace luz
#line 2 "src/data-structure/segment-tree/presets/range-chmin-query-solver.hpp"
#line 2 "src/data-structure/segment-tree/presets/monoid/operator-structure-chmin.hpp"
#include <algorithm>
#include <limits>
namespace luz::monoid {
template < typename T >
class RangeChminQueryMonoid {
static constexpr T identity_{std::numeric_limits< T >::max()};
public:
using value_type = T;
static constexpr T operation(T a, T b) {
return std::min(a, b);
}
static constexpr T identity() {
return identity_;
}
};
} // namespace luz::monoid
#line 2 "src/data-structure/segment-tree/range-mapping-point-fold-segment-tree.hpp"
#line 2 "src/cpp-template/header/rep.hpp"
#line 2 "src/cpp-template/header/size-alias.hpp"
#include <cstddef>
namespace luz {
using isize = std::ptrdiff_t;
using usize = std::size_t;
} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"
#line 6 "src/cpp-template/header/rep.hpp"
namespace luz {
struct rep {
struct itr {
usize i;
constexpr itr(const usize i) noexcept: i(i) {}
void operator++() noexcept {
++i;
}
constexpr usize operator*() const noexcept {
return i;
}
constexpr bool operator!=(const itr x) const noexcept {
return i != x.i;
}
};
const itr f, l;
constexpr rep(const usize f, const usize l) noexcept
: f(std::min(f, l)),
l(l) {}
constexpr auto begin() const noexcept {
return f;
}
constexpr auto end() const noexcept {
return l;
}
};
struct rrep {
struct itr {
usize i;
constexpr itr(const usize i) noexcept: i(i) {}
void operator++() noexcept {
--i;
}
constexpr usize operator*() const noexcept {
return i;
}
constexpr bool operator!=(const itr x) const noexcept {
return i != x.i;
}
};
const itr f, l;
constexpr rrep(const usize f, const usize l) noexcept
: f(l - 1),
l(std::min(f, l) - 1) {}
constexpr auto begin() const noexcept {
return f;
}
constexpr auto end() const noexcept {
return l;
}
};
} // namespace luz
#line 2 "src/utility/bit/bit-width.hpp"
#line 2 "src/cpp-template/header/int-alias.hpp"
#include <cstdint>
namespace luz {
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;
} // namespace luz
#line 2 "src/utility/bit/popcount.hpp"
#line 5 "src/utility/bit/popcount.hpp"
#include <cassert>
namespace luz {
usize popcount(u64 x) {
assert(__cplusplus <= 201703L);
#ifdef __GNUC__
return __builtin_popcountll(x);
#endif
x -= (x >> 1) & 0x5555555555555555;
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
x += (x >> 4) & 0x0f0f0f0f0f0f0f0f;
return x * 0x0101010101010101 >> 56 & 0x7f;
}
} // namespace luz
#line 6 "src/utility/bit/bit-width.hpp"
#line 8 "src/utility/bit/bit-width.hpp"
namespace luz {
usize bit_width(u64 x) {
assert(__cplusplus <= 201703L);
if (x == 0) {
return 0;
}
#ifdef __GNUC__
return 64 - __builtin_clzll(x);
#endif
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
return popcount(x);
}
} // namespace luz
#line 2 "src/utility/bit/count-trailing-0s.hpp"
#line 6 "src/utility/bit/count-trailing-0s.hpp"
#line 8 "src/utility/bit/count-trailing-0s.hpp"
namespace luz {
usize countr_zero(u64 x) {
assert(__cplusplus <= 201703L);
if (x == 0) {
return 64;
}
#ifdef __GNUC__
return __builtin_ctzll(x);
#endif
return popcount((x & -x) - 1);
}
} // namespace luz
#line 7 "src/data-structure/segment-tree/range-mapping-point-fold-segment-tree.hpp"
#line 9 "src/data-structure/segment-tree/range-mapping-point-fold-segment-tree.hpp"
#include <vector>
namespace luz {
template < class operator_structure >
class RangeMappingPointFoldSegmentTree {
using O = operator_structure;
using OT = typename O::value_type;
std::vector< OT > tree;
void evaluate_lazy(OT &x, const OT &y) {
x = O::operation(x, y);
}
void propagate(const usize index) {
evaluate_lazy(tree[index << 1 | 0], tree[index]);
evaluate_lazy(tree[index << 1 | 1], tree[index]);
tree[index] = O::identity();
}
void propagate_bound(const usize index) {
if (index == 0) return;
const usize l = countr_zero(index) + 1;
const usize r = bit_width(index);
for (usize i: rrep(l, r)) {
propagate(index >> i);
}
}
public:
using value_type = OT;
RangeMappingPointFoldSegmentTree() = default;
explicit RangeMappingPointFoldSegmentTree(const usize n)
: tree(n * 2, O::identity()) {}
explicit RangeMappingPointFoldSegmentTree(const usize n, OT v)
: RangeMappingPointFoldSegmentTree(n) {
build(std::vector< OT >(n, v));
}
explicit RangeMappingPointFoldSegmentTree(
const std::vector< OT > &vs)
: RangeMappingPointFoldSegmentTree(vs.size()) {
build(vs);
}
void build(const std::vector< OT > &vs) {
for (usize i: rep(0, vs.size())) {
tree[i + size()] = vs[i];
}
}
usize size() const {
return tree.size() / 2;
}
void set(usize index, const OT x) {
assert(index < size());
index += size();
const usize l = 1;
const usize r = bit_width(index);
for (usize i: rrep(l, r)) {
propagate(index >> i);
}
tree[index] = x;
}
void apply(usize index, const OT &x) {
return apply(index, index + 1, x);
}
void apply(usize first, usize last, const OT &x) {
assert(first <= last);
assert(last <= size());
first += size();
last += size();
propagate_bound(first);
propagate_bound(last);
while (first != last) {
if (first & 1) {
evaluate_lazy(tree[first], x);
first += 1;
}
first >>= 1;
if (last & 1) {
last -= 1;
evaluate_lazy(tree[last], x);
}
last >>= 1;
}
}
OT fold(usize index) {
assert(index < size());
index += size();
OT result = tree[index];
while (index != 1) {
index >>= 1;
evaluate_lazy(result, tree[index]);
}
return result;
}
};
template < class operator_structure >
using DualSegmentTree =
RangeMappingPointFoldSegmentTree< operator_structure >;
} // namespace luz
#line 5 "src/data-structure/segment-tree/presets/range-chmin-query-solver.hpp"
namespace luz {
template < typename T >
using RangeChminQuerySolver =
DualSegmentTree< monoid::RangeChminQueryMonoid< T > >;
} // namespace luz