verify/library_checker/data_structure/static_rmq.test.cpp

View this file on GitHub
Last update: 2025-02-05 15:45:56+09:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include "../../../src/template/template.hpp"
#include "../../../src/data_structure/sparse_table.hpp"
int op(int x, int y) {
    return min(x, y);
}
int e() {
    return 1e9;
}
int main(void) {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    rep(i, 0, n) {
        cin >> a[i];
    }
    SparseTable<int, op, e> st(a);
    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << st.prod(l, r) << '\n';
    }
}

#line 1 "verify/library_checker/data_structure/static_rmq.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/data_structure/sparse_table.hpp"
template <typename S, auto op, auto e>
struct SparseTable {
    SparseTable(const vector<S>& v)
        : n((int)v.size()) {
        const int b = 32 - __builtin_clz(n);
        table.assign(b, vector<S>(n, e()));
        table[0] = v;
        for(int i = 1; i < b; ++i) {
            const int w = 1 << (i - 1);
            for(int j = 0; j + w * 2 <= n; ++j) {
                table[i][j] = op(table[i - 1][j], table[i - 1][j + w]);
            }
        }
    }
    S prod(const int l, const int r) const {
        assert(0 <= l and l <= r and r <= n);
        if(l == r) return e();
        const int b = 31 - __builtin_clz(r - l);
        return op(table[b][l], table[b][r - (1 << b)]);
    }

   private:
    int n;
    vector<vector<S>> table;
};
#line 4 "verify/library_checker/data_structure/static_rmq.test.cpp"
int op(int x, int y) {
    return min(x, y);
}
int e() {
    return 1e9;
}
int main(void) {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    rep(i, 0, n) {
        cin >> a[i];
    }
    SparseTable<int, op, e> st(a);
    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << st.prod(l, r) << '\n';
    }
}