test/ds/sparse_table.test.cpp

• View this file on GitHub
• Last update: 2025-01-11 23:26:54+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• ds/Sparse_table.hpp

Code

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

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


int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (auto &a : A) std::cin >> a;
    po167::Sparse_table<int, op> table(A);
    while (Q--){
        int l, r;
        std::cin >> l >> r;
        std::cout << table.prod(l, r) << "\n";
    }
}

#line 1 "test/ds/sparse_table.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#line 2 "ds/Sparse_table.hpp"
#include <vector>
#include <cassert>
namespace po167{
template<class T, T(*op)(T, T)>
struct Sparse_table{
    int n;
    int depth;
    std::vector<std::vector<T>> val;
    void init(std::vector<T> &v){
        depth = 1;
        n = v.size();
        while ((1 << depth) <= n) depth++;
        val.resize(depth);
        val[0] = v;
        for (int i = 1; i < depth; i++){
            val[i].resize(n);
            for (int j = 0; j <= n - (1 << i); j++){
                val[i][j] = op(val[i - 1][j], val[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    Sparse_table(std::vector<T> v){
        init(v);
    }
    Sparse_table(){}
    // 0 <= l < r <= n
    // if l == r : assert
    T prod(int l, int r){
        assert(0 <= l && l < r && r <= n);
        int z=31-__builtin_clz(r-l);
        return op(val[z][l], val[z][r - (1 << z)]);
    }
};
}
#line 3 "test/ds/sparse_table.test.cpp"
#include <iostream>

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


int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (auto &a : A) std::cin >> a;
    po167::Sparse_table<int, op> table(A);
    while (Q--){
        int l, r;
        std::cin >> l >> r;
        std::cout << table.prod(l, r) << "\n";
    }
}

Back to top page