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_D #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-query-solver.hpp" #include <iostream> namespace luz { void main_() { usize n, q; std::cin >> n >> q; RangeUpdateQuerySolver< 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 i; std::cin >> i; std::cout << seg.fold(i) << std::endl; } } } } // namespace luz int main() { luz::main_(); }
#line 1 "test/aoj/dsl_2_d.test.cpp" // verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_D #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-query-solver.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/range-mapping-point-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-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-update-query-solver.hpp" namespace luz { template < typename T, T ID > using RangeUpdateQuerySolver = DualSegmentTree< monoid::RangeUpdateQueryMonoid< T, ID > >; } // namespace luz #line 7 "test/aoj/dsl_2_d.test.cpp" #include <iostream> namespace luz { void main_() { usize n, q; std::cin >> n >> q; RangeUpdateQuerySolver< 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 i; std::cin >> i; std::cout << seg.fold(i) << std::endl; } } } } // namespace luz int main() { luz::main_(); }