Test/LC/staticrmq/DisjointSparseTable.test.cpp

View this file on GitHub
Last update: 2025-04-17 19:44:48+09:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include "../../../Src/DataStructure/SparseTable/DisjointSparseTable.hpp"

#include <iostream>
#include <vector>
struct M {
    using Element = int;
    static Element identity() {
        return (int)1e9;
    }
    static Element operation(Element l, Element r) {
        return std::min(l, r);
    }
};
int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (int& a : A) std::cin >> a;
    zawa::DisjointSparseTable<M> dst{A};
    while (Q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << dst.product(l, r) << '\n';
    }
}

#line 1 "Test/LC/staticrmq/DisjointSparseTable.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#line 2 "Src/DataStructure/SparseTable/DisjointSparseTable.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 2 "Src/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

} // namespace zawa
#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 5 "Src/DataStructure/SparseTable/DisjointSparseTable.hpp"

#include <bit>
#include <cassert>
#line 9 "Src/DataStructure/SparseTable/DisjointSparseTable.hpp"
#include <vector>

namespace zawa {

template <concepts::Monoid M>
class DisjointSparseTable {
public:

    using V = typename M::Element;

    constexpr usize height(usize n) const {
        return std::max(usize{1}, std::bit_width(n) - (usize)std::has_single_bit(n));
    }

    constexpr usize msb(usize n) const {
        assert(n);
        return std::bit_width(n) - 1;
    }

    DisjointSparseTable(std::vector<V>&& A) : m_table(height(A.size())) {
        assert(A.size());
        for (usize i = 1, w = 2 ; i < m_table.size() ; i++, w <<= 1) {
            m_table[i].resize(A.size());
            for (usize j = 0, idx = 0 ; j < A.size() ; j += w, idx++) {
                V prod = M::identity();
                if (idx & 1) { // ->
                    usize m = std::min(A.size() - j, w);
                    for (usize k = 0 ; k < m ; k++) {
                        prod = M::operation(prod, A[j + k]);
                        m_table[i][j + k] = prod;
                    }
                }
                else { // <-
                    usize m = std::min(A.size(), j + w);
                    for (usize k = m ; k-- > j ; ) {
                        prod = M::operation(A[k], prod);
                        m_table[i][k] = prod;
                    }
                }
            }
        }
        m_table[0] = std::move(A);
    }

    DisjointSparseTable(const std::vector<V>& A) : DisjointSparseTable(std::vector<V>{A}) {}

    template <std::input_iterator It>
    DisjointSparseTable(It first, It last) : DisjointSparseTable(std::vector(first, last)) {}

    V product(usize l, usize r) const {
        assert(l <= r and r <= m_table[0].size());
        if (l == r) return M::identity();
        if (l + 1 == r) return m_table[0][l];
        usize y = msb(l xor --r);
        return M::operation(m_table[y][l], m_table[y][r]);
    }

private:

    std::vector<std::vector<V>> m_table;
};

} // namespace zawa
#line 4 "Test/LC/staticrmq/DisjointSparseTable.test.cpp"

#include <iostream>
#line 7 "Test/LC/staticrmq/DisjointSparseTable.test.cpp"
struct M {
    using Element = int;
    static Element identity() {
        return (int)1e9;
    }
    static Element operation(Element l, Element r) {
        return std::min(l, r);
    }
};
int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (int& a : A) std::cin >> a;
    zawa::DisjointSparseTable<M> dst{A};
    while (Q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << dst.product(l, r) << '\n';
    }
}