test/library_checker/data_structure/static_rmq_2.test.cpp

• View this file on GitHub
• Last update: 2025-01-09 22:06:55+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• Disjoint Sparse Table (lib/data_structure/disjoint_sparse_table.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <bits/stdc++.h>
using namespace std;

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

int op(int x, int y){
    return min(x, y);
}

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];
    }
    DisjointSparseTable<int, op> dst(a);
    for(int i = 0; i < q; i++){
        int l, r; cin >> l >> r;
        cout << dst.query(l, r - 1) << '\n';
    }
}

#line 1 "test/library_checker/data_structure/static_rmq_2.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <bits/stdc++.h>
using namespace std;

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

/**
 * @brief Disjoint Sparse Table
 * @see https://noshi91.hatenablog.com/entry/2018/05/08/183946
 */

#line 10 "lib/data_structure/disjoint_sparse_table.hpp"

template <typename T, T (*op)(T, T)>
struct DisjointSparseTable{
    int n, log2;
    std::vector<std::vector<T>> table;
    std::vector<T> val;
    DisjointSparseTable(std::vector<T> &a) : val(a) {
        int len = a.size();
        n = 1, log2 = 0;
        while(n < len){
            n *= 2;
            log2++;
        }
        val.resize(n);
        table = std::vector<std::vector<T>>(log2, std::vector<T>(n));
        init();
    }

    void init(){
        for(int i = 0; i < log2; i++){
            for(int j = 0; j < n; j += (n >> i)){
                int h = n >> (i + 1);
                // h を中心に左右に累積した値を計算
                table[i][j + h] = val[j + h];
                for(int k = j + h + 1; k < j + h * 2; k++){
                    table[i][k] = op(table[i][k - 1], val[k]);
                }
                table[i][j + h - 1] = val[j + h - 1];
                for(int k = j + h - 2; k >= j; k--){
                    table[i][k] = op(val[k], table[i][k + 1]);
                }
            }
        }
    }

    // [l, r]
    T query(int l, int r){
        assert(l <= r);
        if(l == r){
            return val[l];
        }
        // またぐ場所の計算
        int d = __builtin_clz(l ^ r) - (32 - log2);
        return op(table[d][l], table[d][r]);
    }
};
#line 6 "test/library_checker/data_structure/static_rmq_2.test.cpp"

int op(int x, int y){
    return min(x, y);
}

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];
    }
    DisjointSparseTable<int, op> dst(a);
    for(int i = 0; i < q; i++){
        int l, r; cin >> l >> r;
        cout << dst.query(l, r - 1) << '\n';
    }
}

Back to top page