tests/disjoint_sparse_table.test.cpp

• View this file on GitHub
• Last update: 2025-02-10 20:05:30+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• Bit width required to represent a given integer (tools/bit_width.hpp)
• $\left\lceil \log_2(x) \right\rceil$ (tools/ceil_log2.hpp)
• Disjoint sparse table (tools/disjoint_sparse_table.hpp)
• $\left\lfloor \log_2(x) \right\rfloor$ (tools/floor_log2.hpp)
• std::gcd(m, n) extended for my library (tools/gcd.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• std::is_signed extended for tools::int128_t and tools::uint128_t (tools/is_signed.hpp)
• std::make_unsigned extended for tools::int128_t and tools::uint128_t (tools/make_unsigned.hpp)
• Typical monoids (tools/monoid.hpp)
• $2^x$ (tools/pow2.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/staticrmq

#include <iostream>
#include "tools/monoid.hpp"
#include "tools/disjoint_sparse_table.hpp"

using ll = long long;

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

  ll N, Q;
  std::cin >> N >> Q;
  std::vector<ll> a(N);
  for (auto& a_i : a) {
    std::cin >> a_i;
  }

  tools::disjoint_sparse_table<tools::monoid::min<ll>> dst(a.begin(), a.end());
  for (ll q = 0; q < Q; ++q) {
    ll l, r;
    std::cin >> l >> r;
    std::cout << dst.prod(l, r) << '\n';
  }

  return 0;
}

#line 1 "tests/disjoint_sparse_table.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/staticrmq

#include <iostream>
#line 1 "tools/monoid.hpp"



#include <type_traits>
#include <algorithm>
#include <limits>
#include <cassert>
#line 1 "tools/gcd.hpp"



#line 5 "tools/gcd.hpp"
#include <numeric>

namespace tools {
  template <typename M, typename N>
  constexpr ::std::common_type_t<M, N> gcd(const M m, const N n) {
    return ::std::gcd(m, n);
  }
}


#line 9 "tools/monoid.hpp"

namespace tools {
  namespace monoid {
    template <typename M, M ...dummy>
    struct max;

    template <typename M>
    struct max<M> {
      static_assert(::std::is_arithmetic_v<M>, "M must be a built-in arithmetic type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return ::std::max(lhs, rhs);
      }
      static T e() {
        if constexpr (::std::is_integral_v<M>) {
          return ::std::numeric_limits<M>::min();
        } else {
          return -::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    struct max<M, E> {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        assert(E <= lhs);
        assert(E <= rhs);
        return ::std::max(lhs, rhs);
      }
      static T e() {
        return E;
      }
    };

    template <typename M, M ...dummy>
    struct min;

    template <typename M>
    struct min<M> {
      static_assert(::std::is_arithmetic_v<M>, "M must be a built-in arithmetic type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return ::std::min(lhs, rhs);
      }
      static T e() {
        if constexpr (::std::is_integral_v<M>) {
          return ::std::numeric_limits<M>::max();
        } else {
          return ::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    struct min<M, E> {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        assert(lhs <= E);
        assert(rhs <= E);
        return ::std::min(lhs, rhs);
      }
      static T e() {
        return E;
      }
    };

    template <typename M>
    struct multiplies {
    private:
      using VR = ::std::conditional_t<::std::is_arithmetic_v<M>, const M, const M&>;

    public:
      using T = M;
      static T op(VR lhs, VR rhs) {
        return lhs * rhs;
      }
      static T e() {
        return T(1);
      }
    };

    template <>
    struct multiplies<bool> {
      using T = bool;
      static T op(const bool lhs, const bool rhs) {
        return lhs && rhs;
      }
      static T e() {
        return true;
      }
    };

    template <typename M>
    struct gcd {
    private:
      static_assert(!::std::is_arithmetic_v<M> || (::std::is_integral_v<M> && !::std::is_same_v<M, bool>), "If M is a built-in arithmetic type, it must be integral except for bool.");
      using VR = ::std::conditional_t<::std::is_arithmetic_v<M>, const M, const M&>;

    public:
      using T = M;
      static T op(VR lhs, VR rhs) {
        return ::tools::gcd(lhs, rhs);
      }
      static T e() {
        return T(0);
      }
    };

    template <typename M, M E>
    struct update {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return lhs == E ? rhs : lhs;
      }
      static T e() {
        return E;
      }
    };
  }
}


#line 1 "tools/disjoint_sparse_table.hpp"



#include <vector>
#include <cstddef>
#line 7 "tools/disjoint_sparse_table.hpp"
#include <iterator>
#line 1 "tools/ceil_log2.hpp"



#line 1 "tools/bit_width.hpp"



#include <bit>
#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 1 "tools/is_signed.hpp"



#line 5 "tools/is_signed.hpp"

namespace tools {
  template <typename T>
  struct is_signed : ::std::is_signed<T> {};

  template <typename T>
  inline constexpr bool is_signed_v = ::tools::is_signed<T>::value;
}


#line 1 "tools/make_unsigned.hpp"



#line 5 "tools/make_unsigned.hpp"

namespace tools {
  template <typename T>
  struct make_unsigned : ::std::make_unsigned<T> {};

  template <typename T>
  using make_unsigned_t = typename ::tools::make_unsigned<T>::type;
}


#line 10 "tools/bit_width.hpp"

namespace tools {
  template <typename T>
  constexpr int bit_width(T) noexcept;

  template <typename T>
  constexpr int bit_width(const T x) noexcept {
    static_assert(::tools::is_integral_v<T> && !::std::is_same_v<::std::remove_cv_t<T>, bool>);
    if constexpr (::tools::is_signed_v<T>) {
      assert(x >= 0);
      return ::tools::bit_width<::tools::make_unsigned_t<T>>(x);
    } else {
      return ::std::bit_width(x);
    }
  }
}


#line 6 "tools/ceil_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T ceil_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x - 1);
  }
}


#line 1 "tools/pow2.hpp"



#line 6 "tools/pow2.hpp"

namespace tools {

  template <typename T, typename ::std::enable_if<::std::is_unsigned<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(1) << x;
  }

  template <typename T, typename ::std::enable_if<::std::is_signed<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(static_cast<typename ::std::make_unsigned<T>::type>(1) << static_cast<typename ::std::make_unsigned<T>::type>(x));
  }
}


#line 1 "tools/floor_log2.hpp"



#line 6 "tools/floor_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T floor_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x) - 1;
  }
}


#line 12 "tools/disjoint_sparse_table.hpp"

namespace tools {
  template <typename M>
  class disjoint_sparse_table {
  private:
    using T = typename M::T;
    ::std::vector<T> m_value;
    ::std::size_t m_size;
    ::std::size_t m_capacity;
    ::std::size_t m_height;

  public:
    disjoint_sparse_table() = default;
    disjoint_sparse_table(const ::tools::disjoint_sparse_table<M>&) = default;
    disjoint_sparse_table(::tools::disjoint_sparse_table<M>&&) = default;
    ~disjoint_sparse_table() = default;
    ::tools::disjoint_sparse_table<M>& operator=(const ::tools::disjoint_sparse_table<M>&) = default;
    ::tools::disjoint_sparse_table<M>& operator=(::tools::disjoint_sparse_table<M>&&) = default;

    template <typename InputIterator>
    disjoint_sparse_table(const InputIterator& begin, const InputIterator& end) {
      ::std::copy(begin, end, ::std::back_inserter(this->m_value));
      this->m_size = this->m_value.size();
      this->m_height = this->m_size <= 1 ? this->m_size : ::tools::ceil_log2(this->m_size);
      this->m_capacity = this->m_size <= 1 ? this->m_size : ::tools::pow2(this->m_height);
      this->m_value.resize(this->m_height * this->m_capacity);
      ::std::fill(this->m_value.begin() + this->m_size, this->m_value.begin() + this->m_capacity, M::e());

      for (::std::size_t d = 1; d < this->m_height; ++d) {
        const ::std::size_t offset = d * this->m_capacity;
        for (::std::size_t m = ::tools::pow2(d); m < this->m_capacity; m += ::tools::pow2(d + 1)) {
          this->m_value[offset + (m - 1)] = this->m_value[m - 1];
          this->m_value[offset + m] = this->m_value[m];
          for (::std::size_t l = m - 1; l --> m - ::tools::pow2(d);) {
            this->m_value[offset + l] = M::op(this->m_value[l], this->m_value[offset + (l + 1)]);
          }
          for (::std::size_t r = m + 2; r <= m + ::tools::pow2(d); ++r) {
            this->m_value[offset + (r - 1)] = M::op(this->m_value[offset + (r - 2)], this->m_value[r - 1]);
          }
        }
      }
    }

    ::std::size_t size() const {
      return this->m_size;
    }

    T prod(const ::std::size_t l, const ::std::size_t r) const {
      assert(l <= r && r <= this->m_size);
      if (r - l == 0) {
        return M::e();
      } else if (r - l == 1) {
        return this->m_value[l];
      } else {
        const ::std::size_t offset = ::tools::floor_log2(l ^ (r - 1)) * this->m_capacity;
        return M::op(this->m_value[offset + l], this->m_value[offset + (r - 1)]);
      }
    }
  };
}


#line 6 "tests/disjoint_sparse_table.test.cpp"

using ll = long long;

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

  ll N, Q;
  std::cin >> N >> Q;
  std::vector<ll> a(N);
  for (auto& a_i : a) {
    std::cin >> a_i;
  }

  tools::disjoint_sparse_table<tools::monoid::min<ll>> dst(a.begin(), a.end());
  for (ll q = 0; q < Q; ++q) {
    ll l, r;
    std::cin >> l >> r;
    std::cout << dst.prod(l, r) << '\n';
  }

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	4 ms	3 MB
g++	max_random_00	AC	139 ms	89 MB
g++	max_random_01	AC	132 ms	89 MB
g++	max_random_02	AC	135 ms	89 MB
g++	max_random_03	AC	141 ms	89 MB
g++	max_random_04	AC	134 ms	89 MB
g++	random_00	AC	116 ms	87 MB
g++	random_01	AC	121 ms	89 MB
g++	random_02	AC	75 ms	12 MB
g++	random_03	AC	69 ms	88 MB
g++	random_04	AC	64 ms	86 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	5 ms	4 MB
g++	small_02	AC	5 ms	4 MB
g++	small_03	AC	5 ms	4 MB
g++	small_04	AC	5 ms	4 MB
g++	small_05	AC	5 ms	4 MB
g++	small_06	AC	5 ms	4 MB
g++	small_07	AC	5 ms	4 MB
g++	small_08	AC	5 ms	4 MB
g++	small_09	AC	5 ms	4 MB
g++	small_values_00	AC	150 ms	89 MB
g++	small_width_query_00	AC	186 ms	89 MB
g++	small_width_query_01	AC	185 ms	89 MB
g++	small_width_query_02	AC	205 ms	89 MB
g++	small_width_query_03	AC	200 ms	89 MB
g++	small_width_query_04	AC	202 ms	89 MB

Back to top page