test/SparseTable.test.cpp

• View this file on GitHub
• Last update: 2025-07-04 15:57:54+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• SparseTable.cpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/staticrmq
#include "../SparseTable.cpp"
int op(int a, int b) { return min(a, b); }
int e() { return INT_MAX; }
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    sparsetable<int, op, e> st(a);
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << st.query(l, r) << endl;
    }
}

#line 1 "test/SparseTable.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/staticrmq
#line 1 "SparseTable.cpp"
#include <bits/stdc++.h>
using namespace std;
template <class T, T (*op)(T, T), T (*e)()>
struct sparsetable {
    vector<vector<T>> table;
    vector<int> logtable;
    sparsetable() = default;
    sparsetable(vector<T> v) {
        int len = 0;
        while ((1 << len) <= (int)v.size()) len++;
        table.assign(len, vector<T>(1 << len));
        for (int i = 0; i < (int)v.size(); i++) table[0][i] = v[i];
        for (int i = 1; i < len; i++) {
            for (int j = 0; j + (1 << i) <= (1 << len); j++) {
                table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
        logtable.resize((int)v.size() + 1);
        for (int i = 2; i < (int)logtable.size(); i++) {
            logtable[i] = logtable[(i >> 1)] + 1;
        }
    }
    T query(int l, int r) {
        assert(l <= r);
        if (l == r) return e();
        int len = logtable[r - l];
        return op(table[len][l], table[len][r - (1 << len)]);
    }
};
template <class T, T (*op)(T, T), T (*e)()>
struct disjointsparsetable {
    vector<vector<T>> table;
    vector<int> logtable;
    disjointsparsetable() = default;
    disjointsparsetable(vector<T> v) {
        int len = 0;
        while ((1 << len) <= v.size()) len++;
        table.assign(len, vector<T>(1 << len, e()));
        for (int i = 0; i < (int)v.size(); i++) table[0][i] = v[i];
        for (int i = 1; i < len; i++) {
            int shift = 1 << i;
            for (int j = 0; j < (int)v.size(); j += shift << 1) {
                int t = min(j + shift, (int)v.size());
                table[i][t - 1] = v[t - 1];
                for (int k = t - 2; k >= j; k--) table[i][k] = op(v[k], table[i][k + 1]);
                if (v.size() <= t) break;
                table[i][t] = v[t];
                int r = min(t + shift, (int)v.size());
                for (int k = t + 1; k < r; k++) table[i][k] = op(table[i][k - 1], v[k]);
            }
        }
        logtable.resize(1 << len);
        for (int i = 2; i < logtable.size(); i++) {
            logtable[i] = logtable[(i >> 1)] + 1;
        }
    }
    T query(int l, int r) {
        if (l == r) return e();
        if (l >= --r) return table[0][l];
        int len = logtable[l ^ r];
        return op(table[len][l], table[len][r]);
    };
};
#line 3 "test/SparseTable.test.cpp"
int op(int a, int b) { return min(a, b); }
int e() { return INT_MAX; }
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    sparsetable<int, op, e> st(a);
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << st.query(l, r) << endl;
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	3 MB
g++	max_random_00	AC	906 ms	48 MB
g++	max_random_01	AC	904 ms	48 MB
g++	max_random_02	AC	923 ms	48 MB
g++	max_random_03	AC	892 ms	48 MB
g++	max_random_04	AC	975 ms	48 MB
g++	random_00	AC	744 ms	47 MB
g++	random_01	AC	759 ms	48 MB
g++	random_02	AC	516 ms	8 MB
g++	random_03	AC	188 ms	48 MB
g++	random_04	AC	244 ms	46 MB
g++	small_00	AC	6 ms	4 MB
g++	small_01	AC	6 ms	4 MB
g++	small_02	AC	6 ms	4 MB
g++	small_03	AC	6 ms	3 MB
g++	small_04	AC	6 ms	4 MB
g++	small_05	AC	6 ms	4 MB
g++	small_06	AC	6 ms	4 MB
g++	small_07	AC	6 ms	3 MB
g++	small_08	AC	6 ms	4 MB
g++	small_09	AC	6 ms	3 MB
g++	small_values_00	AC	805 ms	48 MB
g++	small_width_query_00	AC	868 ms	48 MB
g++	small_width_query_01	AC	891 ms	48 MB
g++	small_width_query_02	AC	910 ms	48 MB
g++	small_width_query_03	AC	892 ms	48 MB
g++	small_width_query_04	AC	876 ms	48 MB
clang++	example_00	AC	5 ms	4 MB
clang++	max_random_00	AC	909 ms	48 MB
clang++	max_random_01	AC	958 ms	48 MB
clang++	max_random_02	AC	933 ms	48 MB
clang++	max_random_03	AC	893 ms	48 MB
clang++	max_random_04	AC	888 ms	48 MB
clang++	random_00	AC	756 ms	47 MB
clang++	random_01	AC	778 ms	48 MB
clang++	random_02	AC	513 ms	8 MB
clang++	random_03	AC	202 ms	48 MB
clang++	random_04	AC	254 ms	46 MB
clang++	small_00	AC	6 ms	3 MB
clang++	small_01	AC	6 ms	3 MB
clang++	small_02	AC	5 ms	4 MB
clang++	small_03	AC	5 ms	3 MB
clang++	small_04	AC	5 ms	3 MB
clang++	small_05	AC	5 ms	4 MB
clang++	small_06	AC	5 ms	3 MB
clang++	small_07	AC	5 ms	3 MB
clang++	small_08	AC	5 ms	3 MB
clang++	small_09	AC	5 ms	4 MB
clang++	small_values_00	AC	858 ms	48 MB
clang++	small_width_query_00	AC	859 ms	48 MB
clang++	small_width_query_01	AC	877 ms	48 MB
clang++	small_width_query_02	AC	880 ms	48 MB
clang++	small_width_query_03	AC	911 ms	48 MB
clang++	small_width_query_04	AC	905 ms	48 MB

Back to top page