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_F #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-update-range-minimum-query-solver.hpp" #include <iostream> namespace luz { void main_() { usize n, q; std::cin >> n >> q; RangeUpdateRangeMinimumQuerySolver< i32, -1 > seg(n, (1u << 31) - 1); for ([[maybe_unused]] usize _: rep(0, q)) { usize com; std::cin >> com; if (not com) { usize s, t; i32 x; std::cin >> s >> t >> x; seg.apply(s, t + 1, x); } else { usize s, t; std::cin >> s >> t; std::cout << seg.fold(s, t + 1) << std::endl; } } } } // namespace luz int main() { luz::main_(); }
#line 1 "test/aoj/dsl_2_f/range-minimum.test.cpp" // verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_F #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-update-range-minimum-query-solver.hpp" #line 2 "src/data-structure/segment-tree/presets/monoid/combined-structure-update-minimum.hpp" #line 2 "src/data-structure/segment-tree/presets/monoid/operator-structure-update.hpp" namespace luz::monoid { template < typename T, T ID > class RangeUpdateQueryMonoid { public: using value_type = T; static constexpr T operation(T a, T b) { return b == ID ? a : b; } static constexpr T identity() { return ID; } }; } // namespace luz::monoid #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/monoid/combined-structure-update-minimum.hpp" namespace luz::monoid { template < typename T, T ID > class RangeUpdateRangeMinimumQueryMonoid { using V = RangeMinimumQueryMonoid< T >; using VT = typename V::value_type; using O = RangeUpdateQueryMonoid< T, ID >; using OT = typename O::value_type; public: using value_structure = V; using operator_structure = O; static constexpr T operation(VT a, OT b) { return b == ID ? a : b; } }; } // namespace luz::monoid #line 2 "src/data-structure/segment-tree/range-mapping-range-fold-segment-tree.hpp" #line 2 "src/utility/bit/bit-width.hpp" #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-range-fold-segment-tree.hpp" #line 9 "src/data-structure/segment-tree/range-mapping-range-fold-segment-tree.hpp" #include <vector> namespace luz { template < class combined_structure > class RangeMappingRangeFoldSegmentTree { using C = combined_structure; using V = typename C::value_structure; using VT = typename V::value_type; using O = typename C::operator_structure; using OT = typename O::value_type; class node_type { public: VT value; OT lazy; node_type(const VT value_, const OT lazy_) : value(value_), lazy(lazy_) {} VT get() { return C::operation(value, lazy); } }; std::vector< node_type > tree; void evaluate_lazy(OT &x, const OT &y) { x = O::operation(x, y); } void recalc(usize index) { tree[index].value = V::operation(tree[index << 1 | 0].get(), tree[index << 1 | 1].get()); } void recalc_bound(usize index) { if (index == 0) return; const usize l = countr_zero(index) + 1; const usize r = bit_width(index); for (usize i: rep(l, r)) { recalc(index >> i); } } void propagate(const usize index) { evaluate_lazy(tree[index << 1 | 0].lazy, tree[index].lazy); evaluate_lazy(tree[index << 1 | 1].lazy, tree[index].lazy); tree[index].lazy = 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 = VT; RangeMappingRangeFoldSegmentTree() = default; explicit RangeMappingRangeFoldSegmentTree(const usize n) : tree(n * 2, node_type(V::identity(), O::identity())) {} explicit RangeMappingRangeFoldSegmentTree(const usize n, const VT v) : RangeMappingRangeFoldSegmentTree(n) { build(std::vector< VT >(n, v)); } explicit RangeMappingRangeFoldSegmentTree( const std::vector< VT > &vs) : RangeMappingRangeFoldSegmentTree(vs.size()) { build(vs); } void build(const std::vector< VT > &vs) { usize n = vs.size(); assert(2 * n == tree.size()); for (usize i: rep(0, n)) { tree[i + n] = node_type(vs[i], O::identity()); } for (usize index: rrep(1, n)) { recalc(index); } } usize size() const { return tree.size() / 2; } void set(usize index, const VT 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] = node_type(x, O::identity()); for (usize i: rep(l, r)) { recalc(index >> i); } } 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); const usize c_first = first; const usize c_last = last; while (first != last) { if (first & 1) { evaluate_lazy(tree[first].lazy, x); first += 1; } first >>= 1; if (last & 1) { last -= 1; evaluate_lazy(tree[last].lazy, x); } last >>= 1; } recalc_bound(c_first); recalc_bound(c_last); } VT fold(usize index) { return fold(index, index + 1); } VT fold(usize first, usize last) { assert(first <= last); assert(last <= size()); first += size(); last += size(); propagate_bound(first); recalc_bound(first); propagate_bound(last); recalc_bound(last); VT fold_l = V::identity(); VT fold_r = V::identity(); while (first != last) { if (first & 1) { fold_l = V::operation(fold_l, tree[first].get()); first += 1; } first >>= 1; if (last & 1) { last -= 1; fold_r = V::operation(tree[last].get(), fold_r); } last >>= 1; } return V::operation(fold_l, fold_r); } VT fold_all() { return (size() ? tree[1].get() : V::identity()); } }; template < class combined_structure > using LazySegmentTree = RangeMappingRangeFoldSegmentTree< combined_structure >; } // namespace luz #line 5 "src/data-structure/segment-tree/presets/range-update-range-minimum-query-solver.hpp" namespace luz { template < typename T, T ID > using RangeUpdateRangeMinimumQuerySolver = LazySegmentTree< monoid::RangeUpdateRangeMinimumQueryMonoid< T, ID > >; } // namespace luz #line 7 "test/aoj/dsl_2_f/range-minimum.test.cpp" #include <iostream> namespace luz { void main_() { usize n, q; std::cin >> n >> q; RangeUpdateRangeMinimumQuerySolver< i32, -1 > seg(n, (1u << 31) - 1); for ([[maybe_unused]] usize _: rep(0, q)) { usize com; std::cin >> com; if (not com) { usize s, t; i32 x; std::cin >> s >> t >> x; seg.apply(s, t + 1, x); } else { usize s, t; std::cin >> s >> t; std::cout << seg.fold(s, t + 1) << std::endl; } } } } // namespace luz int main() { luz::main_(); }