test/data_structure/sparse_table/1.test.cpp

• View this file on GitHub
• Last update: 2021-08-11 13:38:32+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• Sparse table (include/data_structure/sparse_table.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

#include "../../../include/data_structure/sparse_table.hpp"

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int N, Q;
  std::cin >> N >> Q;

  std::vector<int> A(N);
  std::copy_n(std::istream_iterator<int>(std::cin), N, std::begin(A));

  const auto F  = [](const int x, const int y) constexpr { return std::min(x, y); };
  const auto st = lib::sparse_table(A, F);

  while (Q--) {
    int l, r;
    std::cin >> l >> r;
    std::cout << st.query(l, r) << '\n';
  }
}

#line 1 "test/data_structure/sparse_table/1.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

#line 1 "include/data_structure/sparse_table.hpp"

//! @file sparse_table.hpp
//! @details Provide a data structure to calculate interval products of associative and idempotent operations.

#ifndef CP_LIBRARY_SPARSE_TABLE_HPP
#define CP_LIBRARY_SPARSE_TABLE_HPP

#include <cassert>
#include <limits>
#include <type_traits>
#line 12 "include/data_structure/sparse_table.hpp"

#ifndef CP_LIBRARY_ASSERT
//! @brief Assert macro
#  define CP_LIBRARY_ASSERT(...) assert(__VA_ARGS__)
#  define CP_LIBRARY_ASSERT_NOT_DEFINED
#endif

namespace lib {

namespace internal::sparse_table_hpp {
  [[nodiscard]] int int_log2(const int n) {
    return std::numeric_limits<int>::digits - __builtin_clz(n);
  }
}  // namespace internal::sparse_table_hpp

//! @brief data structure to calculate interval products of associative and idempotent operations (for static array)
//! @tparam Elem element type (deduced from constructor's parameters but can be set manually if needed)
//! @tparam Func functor type (deduced from constructor's parameters but has to be specified if you set Elem manually)
template <typename Elem, typename Func>
class sparse_table {
private:
  const int length;
  const Func& binary_op;
  std::vector<std::vector<Elem>> table;

public:
  //! @brief Construct a sparse table from source container
  //! @tparam Container container type (deduced from parameter)
  //! @param src source container
  //! @param binary_op_functor functor (must be associative & idempotent)
  //! @note Time complexity: O(N log N) where N = size(src)
  template <typename Container>
  sparse_table(const Container& src, const Func& binary_op_functor)
      : length(static_cast<int>(std::size(src))), binary_op(binary_op_functor) {
    const int M = internal::sparse_table_hpp::int_log2(length) + 1;

    table = std::vector(length, std::vector<Elem>(M));

    for (int i = 0; i < length; ++i)
      table[i][0] = src[i];
    for (int j = 1; j < M; ++j)
      for (int i = 0; i + (1 << j) <= length; ++i)
        table[i][j] = binary_op(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
  }

  //! @return Vector length
  [[nodiscard]] int size() const noexcept {
    return length;
  }

  //! @brief Get the value of the index-th element.
  //! @param index index (0-indexed)
  [[nodiscard]] Elem get(const int index) const {
    return table[index][0];
  }

  //! @param left lower limit of interval (0-indexed)
  //! @param right upper limit of interval (0-indexed)
  //! @return product of the elements of an interval [left, right) (half-open interval)
  //! @note Time complexity: O(1)
  [[nodiscard]] Elem query(const int left, const int right) const {
    CP_LIBRARY_ASSERT(0 <= left && left < right && right <= length);
    const int j = internal::sparse_table_hpp::int_log2(right - left);
    return binary_op(table[left][j], table[right - (1 << j)][j]);
  }
};

//! @brief Deduction guide
template <typename Container, typename Func>
sparse_table(const Container&, const Func&)
  -> sparse_table<std::decay_t<decltype(*std::begin(std::declval<Container>()))>, Func>;

}  // namespace lib

#ifdef CP_LIBRARY_ASSERT_NOT_DEFINED
#  undef CP_LIBRARY_ASSERT
#  undef CP_LIBRARY_ASSERT_NOT_DEFINED
#endif

#endif  // CP_LIBRARY_SPARSE_TABLE_HPP
#line 8 "test/data_structure/sparse_table/1.test.cpp"

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int N, Q;
  std::cin >> N >> Q;

  std::vector<int> A(N);
  std::copy_n(std::istream_iterator<int>(std::cin), N, std::begin(A));

  const auto F  = [](const int x, const int y) constexpr { return std::min(x, y); };
  const auto st = lib::sparse_table(A, F);

  while (Q--) {
    int l, r;
    std::cin >> l >> r;
    std::cout << st.query(l, r) << '\n';
  }
}

Back to top page