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/ITP1_1_A #include "src/data-structure/segment-tree/point-mapping-range-fold-segment-tree.hpp" #include "src/cpp-template/header/int-alias.hpp" #include "src/cpp-template/header/size-alias.hpp" #include <cassert> #include <iostream> #include <numeric> #include <typeinfo> #include <vector> namespace luz { template < typename T > class Monoid { static constexpr T identity_{}; public: using value_type = T; static constexpr T operation(T a, T b) { return a + b; } static constexpr T identity() { return identity_; } }; constexpr usize small = (usize)1 << 3; constexpr usize medium = (usize)1 << 8; constexpr usize large = (usize)1 << 24; template < typename V > void unit_test(usize n) { std::vector< i32 > as(n); std::iota(as.begin(), as.end(), 0); std::cerr << " constructor : " << std::flush; SegmentTree< V > seg(n); std::cerr << "done" << std::endl; std::cerr << " build() : " << std::flush; seg.build(as); std::cerr << "done" << std::endl; std::cerr << " size() : " << std::flush; assert(seg.size() == as.size()); std::cerr << "done" << std::endl; std::cerr << " fold(i), set(i, x) : " << std::flush; for (usize i: rep(0, n)) { assert(seg.fold(i) == as[i]); as[i] = n - i; seg.set(i, as[i]); assert(seg.fold(i) == as[i]); } std::cerr << "done" << std::endl; if (n <= medium + 1) { std::cerr << " fold(l, r) : " << std::flush; for (usize l: rep(0, n)) for (usize r: rep(l, n + 1)) { i32 sum = V::identity(); for (usize i: rep(l, r)) { sum = V::operation(sum, as[i]); } assert(seg.fold(l, r) == sum); } std::cerr << "done" << std::endl; } std::cerr << " fold_all() : " << std::flush; assert(seg.fold_all() == seg.fold(0, n)); std::cerr << "done" << std::endl; } template < class value_type > void unit_test() { std::vector< usize > ns({small - 1, small, small + 1, medium - 1, medium, medium + 1, large - 1, large, large + 1}); std::cerr << "type : " << typeid(value_type).name() << std::endl; for (const usize &n: ns) { std::cerr << " n = " << n << " : " << std::endl; unit_test< value_type >(n); std::cerr << " done" << std::endl; } } void main_() { unit_test< Monoid< i32 > >(); std::cout << "Hello World" << std::endl; } } // namespace luz int main() { luz::main_(); }
#line 1 "unit-test/data-structure/segment-tree/point-mapping-range-fold-segment-tree.test.cpp" // verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ITP1_1_A #line 2 "src/data-structure/segment-tree/point-mapping-range-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" #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 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 4 "unit-test/data-structure/segment-tree/point-mapping-range-fold-segment-tree.test.cpp" #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 7 "unit-test/data-structure/segment-tree/point-mapping-range-fold-segment-tree.test.cpp" #line 9 "unit-test/data-structure/segment-tree/point-mapping-range-fold-segment-tree.test.cpp" #include <iostream> #include <numeric> #include <typeinfo> #line 13 "unit-test/data-structure/segment-tree/point-mapping-range-fold-segment-tree.test.cpp" namespace luz { template < typename T > class Monoid { static constexpr T identity_{}; public: using value_type = T; static constexpr T operation(T a, T b) { return a + b; } static constexpr T identity() { return identity_; } }; constexpr usize small = (usize)1 << 3; constexpr usize medium = (usize)1 << 8; constexpr usize large = (usize)1 << 24; template < typename V > void unit_test(usize n) { std::vector< i32 > as(n); std::iota(as.begin(), as.end(), 0); std::cerr << " constructor : " << std::flush; SegmentTree< V > seg(n); std::cerr << "done" << std::endl; std::cerr << " build() : " << std::flush; seg.build(as); std::cerr << "done" << std::endl; std::cerr << " size() : " << std::flush; assert(seg.size() == as.size()); std::cerr << "done" << std::endl; std::cerr << " fold(i), set(i, x) : " << std::flush; for (usize i: rep(0, n)) { assert(seg.fold(i) == as[i]); as[i] = n - i; seg.set(i, as[i]); assert(seg.fold(i) == as[i]); } std::cerr << "done" << std::endl; if (n <= medium + 1) { std::cerr << " fold(l, r) : " << std::flush; for (usize l: rep(0, n)) for (usize r: rep(l, n + 1)) { i32 sum = V::identity(); for (usize i: rep(l, r)) { sum = V::operation(sum, as[i]); } assert(seg.fold(l, r) == sum); } std::cerr << "done" << std::endl; } std::cerr << " fold_all() : " << std::flush; assert(seg.fold_all() == seg.fold(0, n)); std::cerr << "done" << std::endl; } template < class value_type > void unit_test() { std::vector< usize > ns({small - 1, small, small + 1, medium - 1, medium, medium + 1, large - 1, large, large + 1}); std::cerr << "type : " << typeid(value_type).name() << std::endl; for (const usize &n: ns) { std::cerr << " n = " << n << " : " << std::endl; unit_test< value_type >(n); std::cerr << " done" << std::endl; } } void main_() { unit_test< Monoid< i32 > >(); std::cout << "Hello World" << std::endl; } } // namespace luz int main() { luz::main_(); }