verify/Datastructure_DST.test.cpp

• View this file on GitHub
• Last update: 2025-02-28 10:35:38+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• disjoint_sparse_table (Datastructure/disjoint_sparse_table.hpp)
• verify用テンプレート (Utility/template.hpp)

Code

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

using S = int;
S op(S l, S r) { return min(l, r); }
S e() { return INT_MAX; }
using stable = disjoint_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_DST.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/disjoint_sparse_table.hpp"
template <class S, S (*op)(S, S), S (*e)()> struct disjoint_sparse_table {
    vector<vector<S>> d;
    bool built = false;
    int n, lg;
    vector<S> v;

  private:
    int msb(int x) const { return x == 0 ? -1 : 32 - __builtin_clz(x) - 1; }

    // 潰れた区間もダメ
    S prod_assertless(int l, int r) const {
        if (r - l == 1) return v[l];
        r--;
        int k = msb(l ^ r);
        return op(d[k][l], d[k][r]);
    }

  public:
    disjoint_sparse_table(){}
    disjoint_sparse_table(int n) : disjoint_sparse_table(vector<S>(n, e())) {}
    disjoint_sparse_table(vector<S> const &dat)
        : n(int(dat.size())), lg(0), v(dat) {
        while ((1 << lg) < n) {
            lg++;
        }
        v.resize(1 << lg, e());
    }

    void build() {
        built = true;
        int sz = 1 << lg;
        d.resize(lg, vector<S>(sz, e()));
        for (int k = 0; k < lg; k++) {
            int b = 1 << k;
            for (int mid = b; mid + b <= sz; mid += 2 * b) {
                S sml = e(), smr = e();
                for (int l = mid - 1; l >= mid - b; l--) {
                    sml = op(v[l], sml);
                    d[k][l] = sml;
                }
                for (int r = mid; r < mid + b; r++) {
                    smr = op(smr, v[r]);
                    d[k][r] = smr;
                }
            }
        }
    }

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

    S get(int i) const {
        assert(built);
        return v[i];
    }
    S prod(int l, int r) const {
        assert(built);
        assert(0 <= l && l <= r && r <= n);
        if (r == l) return e();
        if (r - l == 1) return v[l];
        r--;
        int k = msb(l ^ r);
        return op(d[k][l], d[k][r]);
    }

    template <class F> int max_right(int l, F f) const {
        assert(built);
        assert(f(e()));
        if (l == n) return n;
        int ok = l;
        int ng = n;
        while ((ng - ok) > 1) {
            int mi = (ok + ng) / 2;
            if (f(prod_assertless(l, mi))) {
                ok = mi;
            } else {
                ng = mi;
            }
        }
        return ok;
    };

    template <class F> int min_left(int r, F f) const {
        assert(built == true);
        assert(f(e()));
        if (r == 0) return 0;
        int ok = r;
        int ng = -1;
        while ((ok - ng) > 1) {
            int mi = (ok + ng) / 2;
            if (f(prod_assertless(mi, r))) {
                ok = mi;
            } else {
                ng = mi;
            }
        }
        return ok;
    }
};
/*
@brief disjoint_sparse_table
*/
#line 4 "verify/Datastructure_DST.test.cpp"

using S = int;
S op(S l, S r) { return min(l, r); }
S e() { return INT_MAX; }
using stable = disjoint_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';
    }
}

Back to top page