comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: unit-test/data-structure/segment-tree/point-mapping-range-fold-segment-tree.test.cpp

Depends on

Code

// 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_();
}
Back to top page