test/SparseTableDisjoint.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 1000000000; }
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    disjointsparsetable<int, op, e> st(a);
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << st.query(l, r) << "\n";
    }
}

#line 1 "test/SparseTableDisjoint.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/SparseTableDisjoint.test.cpp"
int op(int a, int b) { return min(a, b); }
int e() { return 1000000000; }
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    disjointsparsetable<int, op, e> st(a);
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << st.query(l, r) << "\n";
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	164 ms	48 MB
g++	max_random_01	AC	168 ms	48 MB
g++	max_random_02	AC	163 ms	48 MB
g++	max_random_03	AC	162 ms	48 MB
g++	max_random_04	AC	161 ms	48 MB
g++	random_00	AC	134 ms	47 MB
g++	random_01	AC	142 ms	48 MB
g++	random_02	AC	77 ms	8 MB
g++	random_03	AC	61 ms	48 MB
g++	random_04	AC	65 ms	46 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	4 ms	4 MB
g++	small_04	AC	4 ms	4 MB
g++	small_05	AC	4 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	148 ms	48 MB
g++	small_width_query_00	AC	171 ms	48 MB
g++	small_width_query_01	AC	170 ms	48 MB
g++	small_width_query_02	AC	176 ms	48 MB
g++	small_width_query_03	AC	170 ms	48 MB
g++	small_width_query_04	AC	176 ms	48 MB
clang++	example_00	AC	5 ms	4 MB
clang++	max_random_00	AC	160 ms	48 MB
clang++	max_random_01	AC	172 ms	48 MB
clang++	max_random_02	AC	160 ms	48 MB
clang++	max_random_03	AC	165 ms	48 MB
clang++	max_random_04	AC	160 ms	48 MB
clang++	random_00	AC	136 ms	47 MB
clang++	random_01	AC	149 ms	48 MB
clang++	random_02	AC	82 ms	8 MB
clang++	random_03	AC	60 ms	48 MB
clang++	random_04	AC	65 ms	47 MB
clang++	small_00	AC	5 ms	4 MB
clang++	small_01	AC	4 ms	4 MB
clang++	small_02	AC	4 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	158 ms	48 MB
clang++	small_width_query_00	AC	196 ms	48 MB
clang++	small_width_query_01	AC	187 ms	48 MB
clang++	small_width_query_02	AC	187 ms	48 MB
clang++	small_width_query_03	AC	182 ms	48 MB
clang++	small_width_query_04	AC	180 ms	48 MB

Back to top page