Test/Library Checker/Data Structure/staticrmq01.test.cpp

• View this file on GitHub
• Last update: 2023-12-31 10:48:42+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• DataStructure/SparseTable.hpp

Code

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

#include <bits/stdc++.h>

#include "DataStructure/SparseTable.hpp"


using namespace std;

int op(int a, int b){ return min(a, b); }
int e(){ return 1 << 30; }

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, Q, l, r;
    cin >> N >> Q;
    vector<int> a(N);
    for(auto &&v : a) cin >> v;
    SparseTable<int, op, e> st(a);
    
    while(Q--){
        cin >> l >> r;
        cout << st.prod(l, r) << '\n';
    }
}

#line 1 "Test/Library Checker/Data Structure/staticrmq01.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include <bits/stdc++.h>

#line 1 "DataStructure/SparseTable.hpp"
template <class T, T (*op)(T, T), T (*e)()> struct SparseTable {
    const int n, LOGV;
    std::vector<std::vector<T>> table;
    std::vector<int> log_table;
    SparseTable(const std::vector<T> &v) : n(v.size()), LOGV(std::__lg(std::max(n, 1)) + 1), 
                                           log_table(n + 1), table(LOGV, std::vector<T>(n)) {
        std::copy(v.begin(), v.end(), table[0].begin());
        for(int i = 1; i < LOGV; i++) {
            for(int j = 0; j + (1 << i) <= n; j++) {
                table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
        for(int i = 2; i <= n; i++) {
            log_table[i] = log_table[i >> 1] + 1;
        }
    }
    T prod(int l, int r){
        assert(0 <= l && l <= r && r <= n);
        if(l == r) return e();
        int b = log_table[r - l];
        return op(table[b][l], table[b][r - (1 << b)]);
    }
};
#line 5 "Test/Library Checker/Data Structure/staticrmq01.test.cpp"

using namespace std;

int op(int a, int b){ return min(a, b); }
int e(){ return 1 << 30; }

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, Q, l, r;
    cin >> N >> Q;
    vector<int> a(N);
    for(auto &&v : a) cin >> v;
    SparseTable<int, op, e> st(a);
    
    while(Q--){
        cin >> l >> r;
        cout << st.prod(l, r) << '\n';
    }
}

Back to top page