This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub luzhiled1333/comp-library
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_A #include "src/cpp-template/header/int-alias.hpp" #include "src/cpp-template/header/rep.hpp" #include "src/cpp-template/header/size-alias.hpp" #include "src/data-structure/segment-tree/presets/range-minimum-query-solver.hpp" #include <iostream> namespace luz { void main_() { usize n, q; std::cin >> n >> q; RangeMinimumQuerySolver< i32 > seg(n); for ([[maybe_unused]] usize _: rep(0, q)) { usize com, x, y; std::cin >> com >> x >> y; if (not com) { seg.set(x, y); } else { std::cout << seg.fold(x, y + 1) << std::endl; } } } } // namespace luz int main() { luz::main_(); }
#line 1 "test/aoj/dsl_2_a.test.cpp" // verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_A #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/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" #include <algorithm> 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/data-structure/segment-tree/presets/range-minimum-query-solver.hpp" #line 2 "src/data-structure/segment-tree/point-mapping-range-fold-segment-tree.hpp" #line 5 "src/data-structure/segment-tree/point-mapping-range-fold-segment-tree.hpp" #include <cassert> #include <vector> namespace luz { template < class value_structure > class PointMappingRangeFoldSegmentTree { using V = value_structure; using VT = typename V::value_type; std::vector< VT > tree; void evaluate(usize index) { tree[index] = V::operation(tree[index << 1 | 0], tree[index << 1 | 1]); } public: using value_type = VT; PointMappingRangeFoldSegmentTree() = default; explicit PointMappingRangeFoldSegmentTree(const usize n) : tree(n * 2, V::identity()) {} explicit PointMappingRangeFoldSegmentTree(const usize n, VT v) : PointMappingRangeFoldSegmentTree(n) { build(std::vector< VT >(n, v)); } explicit PointMappingRangeFoldSegmentTree( const std::vector< VT > &vs) : PointMappingRangeFoldSegmentTree(vs.size()) { build(vs); } void build(const std::vector< VT > &vs) { usize n = vs.size(); assert(2 * n == tree.size()); std::copy(vs.begin(), vs.end(), tree.begin() + n); for (usize index: rrep(1, n)) { evaluate(index); } } usize size() const { return tree.size() / 2; } void set(usize index, const VT x) { assert(index < size()); index += size(); tree[index] = x; while (index != 1) { index >>= 1; evaluate(index); } } VT fold(usize index) const { assert(index < size()); return tree[index + size()]; } VT fold(usize first, usize last) const { assert(first <= last); assert(last <= size()); first += size(); last += size(); VT fold_l = V::identity(); VT fold_r = V::identity(); while (first != last) { if (first & 1) { fold_l = V::operation(fold_l, tree[first]); first += 1; } first >>= 1; if (last & 1) { last -= 1; fold_r = V::operation(tree[last], fold_r); } last >>= 1; } return V::operation(fold_l, fold_r); } VT fold_all() const { return (size() ? tree[1] : V::identity()); } }; template < class value_structure > using SegmentTree = PointMappingRangeFoldSegmentTree< value_structure >; } // namespace luz #line 2 "src/data-structure/segment-tree/presets/monoid/value-structure-minimum.hpp" #line 4 "src/data-structure/segment-tree/presets/monoid/value-structure-minimum.hpp" #include <limits> namespace luz::monoid { template < typename T > class RangeMinimumQueryMonoid { 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 5 "src/data-structure/segment-tree/presets/range-minimum-query-solver.hpp" namespace luz { template < typename T > using RangeMinimumQuerySolver = SegmentTree< monoid::RangeMinimumQueryMonoid< T > >; } // namespace luz #line 7 "test/aoj/dsl_2_a.test.cpp" #include <iostream> namespace luz { void main_() { usize n, q; std::cin >> n >> q; RangeMinimumQuerySolver< i32 > seg(n); for ([[maybe_unused]] usize _: rep(0, q)) { usize com, x, y; std::cin >> com >> x >> y; if (not com) { seg.set(x, y); } else { std::cout << seg.fold(x, y + 1) << std::endl; } } } } // namespace luz int main() { luz::main_(); }