test/data_structure/staticrmq.0.test.cpp

View this file on GitHub
Last update: 2025-01-19 15:28:01+08:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

Code

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

#include "monoid.hpp"
#include "sparse_table.hpp"
#include <iostream>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    std::vector<int> V(n);
    for (int i = 0; i < n; ++i) std::cin >> V[i];
    SparseTable st(V, Monoid([](int a, int b) { return a < b ? a : b; }, -1));
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << st.query(l, r) << '\n';
    }
    return 0;
}

#line 1 "test/data_structure/staticrmq.0.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#line 2 "monoid.hpp"

#include <type_traits>

template<typename Tp, typename Op,
         std::enable_if_t<std::is_invocable_r_v<Tp, Op, const Tp &, const Tp &>, int> = 0>
class Monoid {
public:
    Op F;
    Tp Id;

    explicit Monoid(Op F, const Tp &Id = {}) : F(F), Id(Id) {}

    const Tp &id() const { return Id; }
    Tp operator()(const Tp &L, const Tp &R) const { return F(L, R); }
};
#line 2 "sparse_table.hpp"

#line 4 "sparse_table.hpp"
#include <cassert>
#include <vector>

template<typename Tp, typename Op> class SparseTable {
public:
    const int N;
    const Monoid<Tp, Op> M;
    std::vector<Tp> T;

    SparseTable(const std::vector<Tp> &V, const Monoid<Tp, Op> &M) : N(V.size()), M(M) {
        int LogN = 0;
        while ((1 << LogN) < N) ++LogN;
        T.resize((LogN + 1) * N);
        for (int i = 0; i < N; ++i) T[i] = V[i];
        for (int i = 1; i <= LogN; ++i) {
            auto P = T.begin() + (i - 1) * N, C = P + N;
            for (int j = 0; j < N - (1 << i) + 1; ++j) C[j] = M(P[j], P[j + (1 << (i - 1))]);
        }
    }

    // returns M(V[L],...,V[R-1])
    Tp query(int L, int R) const {
        assert(L <= R);
        if (L == R) return M.id();
        const int lv = 31 - __builtin_clz(R - L);
        return M(T[lv * N + L], T[lv * N + R - (1 << lv)]);
    }
};
#line 5 "test/data_structure/staticrmq.0.test.cpp"
#include <iostream>
#line 7 "test/data_structure/staticrmq.0.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    std::vector<int> V(n);
    for (int i = 0; i < n; ++i) std::cin >> V[i];
    SparseTable st(V, Monoid([](int a, int b) { return a < b ? a : b; }, -1));
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << st.query(l, r) << '\n';
    }
    return 0;
}