test/library_checker/data_structure/static_rmq_1.test.cpp

View this file on GitHub
Last update: 2024-11-15 15:44:55+09:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

Sparse Table (lib/data_structure/sparse_table.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <iostream>

#include "../../../lib/data_structure/sparse_table.hpp"

using namespace std;

int op(int a, int b){
    return min(a, b);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q; cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    SparseTable<int, op> rmq(a);
    while(q--){
        int l, r; cin >> l >> r;
        cout << rmq.query(l, r) << "\n";
    }
}

#line 1 "test/library_checker/data_structure/static_rmq_1.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <iostream>

#line 2 "lib/data_structure/sparse_table.hpp"

/**
 * @brief Sparse Table
 */

#include <vector>
#include <cassert>

template <class T, T (*op)(T, T)>
struct SparseTable{
    std::vector<std::vector<T>> _table;
    std::vector<int> _log2;

    SparseTable(const std::vector<T> &v){
        const int n = v.size();
        _log2.assign(n + 1, 0);
        for(int i = 2; i <= n; i++) _log2[i] = _log2[i >> 1] + 1;
        _table.assign(_log2[n] + 1, std::vector<T>(n));
        for(int i = 0; i < n; i++) _table[0][i] = v[i];
        for(int k = 1; k <= _log2[n]; k++){
            for(int i = 0; i + (1 << k) <= n; i++)
                _table[k][i] = op(_table[k - 1][i], _table[k - 1][i + (1 << (k - 1))]);
        }
    }

    inline T query(const int &l, const int &r) const {
        assert(l < r);
        const int ex = _log2[r - l];
        return op(_table[ex][l], _table[ex][r - (1 << ex)]);
    }
};
#line 5 "test/library_checker/data_structure/static_rmq_1.test.cpp"

using namespace std;

int op(int a, int b){
    return min(a, b);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q; cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    SparseTable<int, op> rmq(a);
    while(q--){
        int l, r; cin >> l >> r;
        cout << rmq.query(l, r) << "\n";
    }
}