verify/Datastructure_sprase_table.test.cpp

View this file on GitHub
Last update: 2025-01-10 00:00:54+09:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include "../Utility/template.hpp"
#include "../Datastructure/sparse_table.hpp"

using S = int;
S op(S l, S r) { return min(l, r); }
S e() { return INT_MAX; }
using stable = sparse_table<S, op, e>;

int main() {
    int n, q;
    cin >> n >> q;
    vec<S> A(n);
    rep(i, 0, n) cin >> A[i];
    stable st(A);
    stable st2(n);
    rep(i, 0, n) st2.set(i, A[i]);
    st.build(); st2.build();
    while(q--) {
        int l, r;
        cin >> l >> r;
        assert(st.prod(l, r) == st2.prod(l, r));
        cout << st.prod(l, r) << '\n';
    }
}

#line 1 "verify/Datastructure_sprase_table.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/sparse_table.hpp"
template <class S, S (*op)(S, S), S (*e)()> struct sparse_table {
    vector<vector<S>> d;
    vector<int> lookup;
    bool built = false;
    int n, lg;
    vector<S> v;

    sparse_table(int n) : n(n), v(n, e()) {}

    sparse_table(const vector<S> &v) : n(v.size()), v(v) {}

    void set(int i, S x) {
        assert(0 <= i && i < n);
        assert(built == false);
        v[i] = x;
    }

    void build() {
        n = v.size();
        lg = 0;
        while ((1LL << lg) <= n) lg++;
        d.resize(lg, vector<S>(1LL << lg, e()));
        for (int i = 0; i < n; i++) {
            d[0][i] = v[i];
        }
        for (int i = 1; i < lg; i++) {
            for (int j = 0; j + (1LL << i) <= (1LL << lg); j++) {
                d[i][j] = op(d[i - 1][j], d[i - 1][j + (1LL << (i - 1))]);
            }
        }
        lookup.resize(n + 1);
        for (int i = 2; i < int(lookup.size()); i++) {
            lookup[i] = lookup[i >> 1] + 1;
        }
        built = true;
    }

    S get(int i) {
        assert(0 <= i && i < n);
        return v[i];
    }

    S prod(int l, int r) {
        assert(built == true);
        assert(0 <= l && r <= n);
        if (l >= r) return e();
        int LG = lookup[r - l];
        return op(d[LG][l], d[LG][r - (1LL << LG)]);
    }
};

/*
@brief sparse_table
*/
#line 4 "verify/Datastructure_sprase_table.test.cpp"

using S = int;
S op(S l, S r) { return min(l, r); }
S e() { return INT_MAX; }
using stable = sparse_table<S, op, e>;

int main() {
    int n, q;
    cin >> n >> q;
    vec<S> A(n);
    rep(i, 0, n) cin >> A[i];
    stable st(A);
    stable st2(n);
    rep(i, 0, n) st2.set(i, A[i]);
    st.build(); st2.build();
    while(q--) {
        int l, r;
        cin >> l >> r;
        assert(st.prod(l, r) == st2.prod(l, r));
        cout << st.prod(l, r) << '\n';
    }
}