test/yosupo/ds/disjoint_sparse_table.test.cpp

• View this file on GitHub
• Last update: 2025-12-19 22:22:43+07:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• Disjoint Sparse Table (ds/disjoint_sparse_table.hpp)

Code

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

#include <bits/stdc++.h>
using namespace std;

#include "ds/disjoint_sparse_table.hpp"

struct M {
    using T = int;
    static T id() { return 1.1e9; }
    static T op(T l, T r) { return min(l, r); }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int &i : a) cin >> i;
    DisjointSparseTable<M> st(a);
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << st.prod(l, r) << "\n";
    }
}

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

#include <bits/stdc++.h>
using namespace std;

#line 2 "ds/disjoint_sparse_table.hpp"

template<class M> struct DisjointSparseTable {
    using T = typename M::T;
    DisjointSparseTable(const vector<T> &v) :
        DisjointSparseTable((int)v.size(), [&](int i) -> T { return v[i]; }) {}
    template<class G> DisjointSparseTable(int _n, G &&gen) : n(_n) {
        t.emplace_back(n);
        for (int i = 0; i < n; i++) t[0][i] = gen(i);
        for (int p = 1; 1 << p < n; p++) {
            t.emplace_back(n);
            for (int mid = 1 << p; mid < n; mid += 1 << (p + 1)) {
                t[p][mid - 1] = gen(mid - 1);
                for (int j = mid - 2; j >= mid - (1 << p); j--)
                    t[p][j] = M::op(gen(j), t[p][j + 1]);
                t[p][mid] = gen(mid);
                for (int j = mid + 1; j < min(mid + (1 << p), n); j++)
                    t[p][j] = M::op(t[p][j - 1], gen(j));
            }
        }
    }

    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return M::id();
        r--;
        if (l == r) return t[0][l];
        int p = __builtin_clz(1) - __builtin_clz(l ^ r);
        return M::op(t[p][l], t[p][r]);
    }

  private:
    int n;
    vector<vector<T>> t;
};
#line 7 "test/yosupo/ds/disjoint_sparse_table.test.cpp"

struct M {
    using T = int;
    static T id() { return 1.1e9; }
    static T op(T l, T r) { return min(l, r); }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int &i : a) cin >> i;
    DisjointSparseTable<M> st(a);
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << st.prod(l, r) << "\n";
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	147 ms	43 MB
g++	max_random_01	AC	151 ms	43 MB
g++	max_random_02	AC	144 ms	42 MB
g++	max_random_03	AC	144 ms	43 MB
g++	max_random_04	AC	150 ms	43 MB
g++	random_00	AC	122 ms	34 MB
g++	random_01	AC	123 ms	40 MB
g++	random_02	AC	72 ms	7 MB
g++	random_03	AC	54 ms	37 MB
g++	random_04	AC	52 ms	25 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	4 ms	4 MB
g++	small_02	AC	4 ms	4 MB
g++	small_03	AC	5 ms	4 MB
g++	small_04	AC	5 ms	4 MB
g++	small_05	AC	5 ms	4 MB
g++	small_06	AC	4 ms	4 MB
g++	small_07	AC	4 ms	4 MB
g++	small_08	AC	4 ms	4 MB
g++	small_09	AC	4 ms	4 MB
g++	small_values_00	AC	135 ms	43 MB
g++	small_width_query_00	AC	167 ms	42 MB
g++	small_width_query_01	AC	169 ms	43 MB
g++	small_width_query_02	AC	174 ms	43 MB
g++	small_width_query_03	AC	177 ms	42 MB
g++	small_width_query_04	AC	174 ms	42 MB
clang++	example_00	AC	5 ms	4 MB
clang++	max_random_00	AC	148 ms	42 MB
clang++	max_random_01	AC	148 ms	42 MB
clang++	max_random_02	AC	152 ms	42 MB
clang++	max_random_03	AC	146 ms	42 MB
clang++	max_random_04	AC	150 ms	43 MB
clang++	random_00	AC	118 ms	34 MB
clang++	random_01	AC	127 ms	40 MB
clang++	random_02	AC	77 ms	7 MB
clang++	random_03	AC	56 ms	37 MB
clang++	random_04	AC	52 ms	25 MB
clang++	small_00	AC	5 ms	4 MB
clang++	small_01	AC	5 ms	4 MB
clang++	small_02	AC	5 ms	4 MB
clang++	small_03	AC	4 ms	4 MB
clang++	small_04	AC	4 ms	4 MB
clang++	small_05	AC	4 ms	4 MB
clang++	small_06	AC	4 ms	4 MB
clang++	small_07	AC	4 ms	4 MB
clang++	small_08	AC	4 ms	4 MB
clang++	small_09	AC	4 ms	4 MB
clang++	small_values_00	AC	136 ms	42 MB
clang++	small_width_query_00	AC	181 ms	42 MB
clang++	small_width_query_01	AC	178 ms	43 MB
clang++	small_width_query_02	AC	182 ms	42 MB
clang++	small_width_query_03	AC	174 ms	42 MB
clang++	small_width_query_04	AC	173 ms	42 MB

Back to top page