test/sparse_table/static_rmq.test.cpp

• View this file on GitHub
• Last update: 2025-09-16 22:59:29+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• Sparse Table (sparse_table/sparse_table.hpp)

Code

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

#include "sparse_table/sparse_table.hpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (auto &x : A) {
        std::cin >> x;
    }
    auto op = [](auto a, auto b) { return std::min(a, b); };
    auto e = []() { return std::numeric_limits<int>::max(); };
    sparse_table<int, op, e> S(A);
    while (Q--) {
        int l, r;
        std::cin >> l >> r;
        auto ans = S.prod_idempotent(l, r);
        std::cout << ans << '\n';
    }
}

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

#line 1 "sparse_table/sparse_table.hpp"



#include <bit>
#include <cassert>
#include <type_traits>
#include <vector>

template <typename S, auto op, auto e> struct sparse_table {
    static_assert(std::is_invocable_r_v<S, decltype(op), S, S>,
                  "op must be a function of type S(S, S)");
    static_assert(std::is_invocable_r_v<S, decltype(e)>,
                  "e must be a function of type S()");
    sparse_table(const std::vector<S> &v)
        : n_((int)v.size()), width_(std::bit_width(v.size())),
          table_(width_, std::vector<S>(v.size())) {
        table_[0] = v;
        for (auto i = 1; i < width_; ++i) {
            for (auto j = 0; j + (1 << i) <= n_; ++j) {
                table_[i][j] =
                    op(table_[i - 1][j], table_[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= n_);
        auto sum = e();
        for (auto i = width_ - 1; 0 <= i; --i) {
            if ((1 << i) <= r - l) {
                sum = op(sum, table_[i][l]);
                l += (1 << i);
            }
        }
        return sum;
    }
    S prod_idempotent(int l, int r) {
        assert(0 <= l && l <= r && r <= n_);
        if (l == r) {
            return e();
        }
        auto i = std::bit_width(unsigned(r - l)) - 1;
        return op(table_[i][l], table_[i][r - (1 << i)]);
    }

private:
    int n_, width_;
    std::vector<std::vector<S>> table_;
};


#line 4 "test/sparse_table/static_rmq.test.cpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (auto &x : A) {
        std::cin >> x;
    }
    auto op = [](auto a, auto b) { return std::min(a, b); };
    auto e = []() { return std::numeric_limits<int>::max(); };
    sparse_table<int, op, e> S(A);
    while (Q--) {
        int l, r;
        std::cin >> l >> r;
        auto ans = S.prod_idempotent(l, r);
        std::cout << ans << '\n';
    }
}

Back to top page