algorithm-dev
This documentation is automatically generated by online-judge-tools/verification-helper
verify/yosupo-staticrmp-sparse_table.test.cpp
- View this file on GitHub
- Last update: 2025-07-03 00:41:25+09:00
- Problem: https://judge.yosupo.jp/problem/staticrmq
- Link: View error logs on GitHub Actions
Depends on
algorithm/Math/Algebra/algebra.hpp
Code
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <iostream>
#include <vector>
#include "../algorithm/DataStructure/SegmentTree/sparse_table.hpp"
int main() {
int n;
int q;
std::cin >> n >> q;
std::vector<int> a(n);
for(auto &elem : a) std::cin >> elem;
algorithm::sparse_table::range_minimum_sparse_table<int> table(a.cbegin(), a.cend());
while(q--) {
int l, r;
std::cin >> l >> r;
auto &&ans = table.prod(l, r);
std::cout << ans << "\n";
}
}#line 1 "verify/yosupo-staticrmp-sparse_table.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <iostream>
#include <vector>
#line 1 "algorithm/DataStructure/SegmentTree/sparse_table.hpp"
#include <cassert>
#include <initializer_list>
#line 7 "algorithm/DataStructure/SegmentTree/sparse_table.hpp"
#include <iterator>
#line 9 "algorithm/DataStructure/SegmentTree/sparse_table.hpp"
#line 1 "algorithm/Math/Algebra/algebra.hpp"
#include <algorithm>
#line 6 "algorithm/Math/Algebra/algebra.hpp"
#include <limits>
#include <numeric>
#include <type_traits>
#include <utility>
namespace algorithm {
namespace algebra {
template <typename S>
class Set {
public:
using value_type = S;
protected:
value_type val;
public:
constexpr Set() : val() {}
constexpr Set(const value_type &val) : val(val) {}
constexpr Set(value_type &&val) : val(std::move(val)) {}
friend constexpr bool operator==(const Set &lhs, const Set &rhs) { return lhs.val == rhs.val; }
friend std::istream &operator>>(std::istream &is, Set &rhs) { return is >> rhs.val; }
friend std::ostream &operator<<(std::ostream &os, const Set &rhs) { return os << rhs.val; }
constexpr value_type value() const { return val; }
};
template <typename S, auto op>
class Semigroup : public Set<S> {
static_assert(std::is_invocable_r<S, decltype(op), S, S>::value);
using base_type = Set<S>;
public:
using value_type = typename base_type::value_type;
constexpr Semigroup() : base_type() {}
constexpr Semigroup(const value_type &val) : base_type(val) {}
constexpr Semigroup(value_type &&val) : base_type(std::move(val)) {}
friend constexpr Semigroup operator*(const Semigroup &lhs, const Semigroup &rhs) { return Semigroup(op(lhs.val, rhs.val)); }
static constexpr auto get_op() { return op; }
};
template <typename S, auto op, auto e>
class Monoid : public Semigroup<S, op> {
static_assert(std::is_invocable_r<S, decltype(e)>::value);
using base_type = Semigroup<S, op>;
public:
using value_type = typename base_type::value_type;
constexpr Monoid() : base_type() {}
constexpr Monoid(const value_type &val) : base_type(val) {}
constexpr Monoid(value_type &&val) : base_type(std::move(val)) {}
friend constexpr Monoid operator*(const Monoid &lhs, const Monoid &rhs) { return Monoid(op(lhs.val, rhs.val)); }
static constexpr auto get_e() { return e; }
static constexpr Monoid one() { return Monoid(e()); } // return identity element.
};
template <typename S, auto op, auto e, auto inverse>
class Group : public Monoid<S, op, e> {
static_assert(std::is_invocable_r<S, decltype(inverse), S>::value);
using base_type = Monoid<S, op, e>;
public:
using value_type = typename base_type::value_type;
constexpr Group() : base_type() {}
constexpr Group(const value_type &val) : base_type(val) {}
constexpr Group(value_type &&val) : base_type(std::move(val)) {}
friend constexpr Group operator*(const Group &lhs, const Group &rhs) { return Group(op(lhs.val, rhs.val)); }
static constexpr auto get_inverse() { return inverse; }
static constexpr Group one() { return Group(e()); } // return identity element.
constexpr Group inv() const { return Group(inverse(this->val)); } // return inverse element.
};
template <typename F, auto compose, auto id, typename X, auto mapping>
class OperatorMonoid : public Monoid<F, compose, id> {
static_assert(std::is_invocable_r<X, decltype(mapping), F, X>::value);
using base_type = Monoid<F, compose, id>;
public:
using value_type = typename base_type::value_type;
using acted_value_type = X;
constexpr OperatorMonoid() : base_type() {}
constexpr OperatorMonoid(const value_type &val) : base_type(val) {}
constexpr OperatorMonoid(value_type &&val) : base_type(std::move(val)) {}
friend constexpr OperatorMonoid operator*(const OperatorMonoid &lhs, const OperatorMonoid &rhs) { return OperatorMonoid(compose(lhs.val, rhs.val)); }
static constexpr auto get_mapping() { return mapping; }
static constexpr OperatorMonoid one() { return OperatorMonoid(id()); } // return identity mapping.
constexpr acted_value_type act(const acted_value_type &x) const { return mapping(this->val, x); }
template <class S>
constexpr S act(const S &x) const {
static_assert(std::is_base_of<Set<acted_value_type>, S>::value);
return S(mapping(this->val, x.value()));
}
};
namespace element {
template <typename S>
constexpr auto zero = []() -> S { return S(); };
template <typename S>
constexpr auto one = []() -> S { return 1; };
template <typename S>
constexpr auto min = []() -> S { return std::numeric_limits<S>::min(); };
template <typename S>
constexpr auto max = []() -> S { return std::numeric_limits<S>::max(); };
template <typename S>
constexpr auto one_below_max = []() -> S { return std::numeric_limits<S>::max() - 1; };
template <typename S>
constexpr auto lowest = []() -> S { return std::numeric_limits<S>::lowest(); };
template <typename S>
constexpr auto one_above_lowest = []() -> S { return std::numeric_limits<S>::lowest() + 1; };
} // namespace element
namespace uoperator {
template <typename S>
constexpr auto identity = [](const S &val) -> S { return val; };
template <typename S>
constexpr auto negate = [](const S &val) -> S { return -val; };
} // namespace uoperator
namespace boperator {
template <typename T, typename S = T>
constexpr auto plus = [](const T &lhs, const S &rhs) -> S { return lhs + rhs; };
template <typename T, typename S = T>
constexpr auto mul = [](const T &lhs, const S &rhs) -> S { return lhs * rhs; };
template <typename T, typename S = T>
constexpr auto bit_and = [](const T &lhs, const S &rhs) -> S { return lhs & rhs; };
template <typename T, typename S = T>
constexpr auto bit_or = [](const T &lhs, const S &rhs) -> S { return lhs | rhs; };
template <typename T, typename S = T>
constexpr auto bit_xor = [](const T &lhs, const S &rhs) -> S { return lhs ^ rhs; };
template <typename T, typename S = T>
constexpr auto min = [](const T &lhs, const S &rhs) -> S { return std::min<S>(lhs, rhs); };
template <typename T, typename S = T>
constexpr auto max = [](const T &lhs, const S &rhs) -> S { return std::max<S>(lhs, rhs); };
template <typename T, typename S = T>
constexpr auto gcd = [](const T &lhs, const S &rhs) -> S { return std::gcd(lhs, rhs); };
template <typename T, typename S = T>
constexpr auto lcm = [](const T &lhs, const S &rhs) -> S { return std::lcm(lhs, rhs); };
template <typename F, auto id, typename X = F>
constexpr auto assign_if_not_id = [](const F &lhs, const X &rhs) -> X {
static_assert(std::is_invocable_r<F, decltype(id)>::value);
return (lhs == id() ? rhs : lhs);
};
} // namespace boperator
namespace monoid {
template <typename S>
using minimum = Monoid<S, boperator::min<S>, element::max<S>>;
template <typename S>
using minimum_safe = Monoid<S, boperator::min<S>, element::one_below_max<S>>;
template <typename S>
using maximum = Monoid<S, boperator::max<S>, element::lowest<S>>;
template <typename S>
using maximum_safe = Monoid<S, boperator::max<S>, element::one_above_lowest<S>>;
template <typename S>
using addition = Monoid<S, boperator::plus<S>, element::zero<S>>;
template <typename S>
using multiplication = Monoid<S, boperator::mul<S>, element::one<S>>;
template <typename S>
using bit_xor = Monoid<S, boperator::bit_xor<S>, element::zero<S>>;
} // namespace monoid
namespace group {
template <typename S>
using addition = Group<S, boperator::plus<S>, element::zero<S>, uoperator::negate<S>>;
template <typename S>
using bit_xor = Group<S, boperator::bit_xor<S>, element::zero<S>, uoperator::identity<S>>;
} // namespace group
namespace operator_monoid {
template <typename F, typename X = F>
using assign_for_minimum = OperatorMonoid<
F, boperator::assign_if_not_id<F, element::max<F>>, element::max<F>,
X, boperator::assign_if_not_id<F, element::max<F>, X>>;
template <typename F, typename X = F>
using assign_for_maximum = OperatorMonoid<
F, boperator::assign_if_not_id<F, element::lowest<F>>, element::lowest<F>,
X, boperator::assign_if_not_id<F, element::lowest<F>, X>>;
template <typename F, typename X = F>
using addition = OperatorMonoid<F, boperator::plus<F>, element::zero<F>, X, boperator::plus<F, X>>;
} // namespace operator_monoid
} // namespace algebra
} // namespace algorithm
#line 11 "algorithm/DataStructure/SegmentTree/sparse_table.hpp"
namespace algorithm {
namespace sparse_table {
template <class IdempotentSemigroup>
class SparseTable {
public:
using semigroup_type = IdempotentSemigroup;
using value_type = semigroup_type::value_type;
using size_type = std::size_t;
private:
size_type m_sz; // m_sz:=(要素数).
std::vector<size_type> m_lg; // m_lg[x]:=floor(log2(x)).
std::vector<std::vector<semigroup_type>> m_table; // m_table[k][l]:=(区間[l,l+2^k)の総積).
public:
// constructor. O(N log N).
SparseTable() : m_sz(0), m_lg({0}), m_table({{}}) {}
template <std::input_iterator InputIter>
explicit SparseTable(InputIter first, InputIter last) : m_table(1, std::vector<semigroup_type>(first, last)) {
m_sz = m_table[0].size();
m_lg.assign(m_sz + 1, 0);
for(size_type i = 2; i <= m_sz; ++i) m_lg[i] = m_lg[i >> 1] + 1;
m_table.resize(m_lg[m_sz] + 1);
for(size_type k = 1; k <= m_lg[m_sz]; ++k) {
size_type n = m_sz - (1U << k) + 1;
m_table[k].resize(n);
for(size_type i = 0; i < n; ++i) m_table[k][i] = m_table[k - 1][i] * m_table[k - 1][i + (1U << (k - 1))];
}
}
template <typename T>
explicit SparseTable(std::initializer_list<T> il) : SparseTable(il.begin(), il.end()) {}
// 要素数を取得する．
size_type size() const { return m_sz; }
// k番目の要素を取得する．O(1).
value_type prod(size_type k) const {
assert(k < size());
return m_table[0][k].value();
}
// 区間[l,r)の要素の総積を求める．O(1).
value_type prod(size_type l, size_type r) const {
assert(l < r and r <= size());
size_type k = m_lg[r - l];
return (m_table[k][l] * m_table[k][r - (1U << k)]).value();
}
// 区間全体の要素の総積を求める．O(1).
value_type prod_all() const {
assert(size() > 0);
return (m_table.back().front() * m_table.back().back()).value();
}
friend std::ostream &operator<<(std::ostream &os, const SparseTable &rhs) {
os << "[\n";
for(size_type k = 0; k <= rhs.m_lg.back(); ++k) {
for(int i = 0, end = rhs.m_table[k].size(); i < end; ++i) os << (i == 0 ? " [" : " ") << rhs.m_table[k][i];
os << "]\n";
}
return os << "]";
}
};
template <typename S>
using range_minimum_sparse_table = SparseTable<algebra::Semigroup<S, algebra::boperator::min<S>>>;
template <typename S>
using range_maximum_sparse_table = SparseTable<algebra::Semigroup<S, algebra::boperator::max<S>>>;
template <typename S>
using range_gcd_sparse_table = SparseTable<algebra::Semigroup<S, algebra::boperator::gcd<S>>>;
template <typename S>
using range_lcm_sparse_table = SparseTable<algebra::Semigroup<S, algebra::boperator::lcm<S>>>;
} // namespace sparse_table
} // namespace algorithm
#line 7 "verify/yosupo-staticrmp-sparse_table.test.cpp"
int main() {
int n;
int q;
std::cin >> n >> q;
std::vector<int> a(n);
for(auto &elem : a) std::cin >> elem;
algorithm::sparse_table::range_minimum_sparse_table<int> table(a.cbegin(), a.cend());
while(q--) {
int l, r;
std::cin >> l >> r;
auto &&ans = table.prod(l, r);
std::cout << ans << "\n";
}
}