test/data_structure/StaticRMQ.test.cpp

View this file on GitHub
Last update: 2023-06-29 15:06:40+09:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

Code

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

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

using namespace lib;

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];
    SparseTable<int, op> spt(a);
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << spt.get(l, r) << '\n';
    }
}

#line 1 "test/data_structure/StaticRMQ.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#line 2 "data_structure/sparse_table.hpp"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 4 "data_structure/sparse_table.hpp"

namespace lib {

template <class S, S (*op)(S, S)> struct SparseTable {
    vector<vector<S>> table;
    vector<int> clz;
    SparseTable(const vector<S> &vec) {
        int n = vec.size(), n2 = 0;
        while ((1 << n2) < n) n2++;
        table.resize(n2 + 1);
        rep(i, 0, n2 + 1) {
            table[i].resize(n);
            if (i == 0) {
                rep(j, 0, n) table[i][j] = vec[j];
            } else {
                rep(j, 0, n) {
                    if (j + (1 << (i - 1)) < n)
                        table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
                    else
                        table[i][j] = table[i - 1][j];
                }
            }
        }
        clz.resize(n + 1);
        rep(i, 0, n2 + 1) {
            for (int j = (1 << i); j < (2 << i) && j <= n; j++) {
                clz[j] = i;
            }
        }
    }
    // 単位元を要求しないので if (l >= r) return e()
    // みたいなことをしていない、注意すること！！
    S get(int l, int r) {
        assert(r - l > 0);
        // int lgs = 31 - __builtin_clz((unsigned int)(r-l));
        int lgs = clz[r - l];
        return op(table[lgs][l], table[lgs][r - (1 << lgs)]);
    }
};

}  // namespace lib
#line 5 "test/data_structure/StaticRMQ.test.cpp"

using namespace lib;

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];
    SparseTable<int, op> spt(a);
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << spt.get(l, r) << '\n';
    }
}