This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include "../disjoint_sparse_table.hpp"
#include <iostream>
#include <vector>
using namespace std;
int f(int l, int r) { return l < r ? l : r; };
int main() {
int N, Q;
cin >> N >> Q;
vector<int> A(N);
for (auto &x : A) cin >> x;
disj_sparse_table<int, f> rmq(A);
while (Q--) {
int l, r;
cin >> l >> r;
cout << rmq.prod(l, r) << '\n';
}
}
#line 1 "sparse_table/test/disjoint_sparse_table_rmq.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#line 2 "sparse_table/disjoint_sparse_table.hpp"
#include <algorithm>
#include <cassert>
#include <vector>
// CUT begin
// Disjoint sparse table
// https://discuss.codechef.com/t/tutorial-disjoint-sparse-table/17404
// https://drken1215.hatenablog.com/entry/2018/09/08/162600
// Complexity: O(NlogN) for precalculation, O(1) per query
// - get(l, r): return op(x_l, ..., x_{r - 1})
template <class S, S (*op)(S, S)> struct disj_sparse_table {
int N, sz;
std::vector<std::vector<S>> d;
static int _msb(int x) noexcept { return x == 0 ? 0 : (__builtin_clz(x) ^ 31); }
disj_sparse_table() = default;
disj_sparse_table(const std::vector<S> &seq) : N(seq.size()) {
sz = 1 << (_msb(N - 1) + 1);
d.assign(_msb(sz) + 1, std::vector<S>(sz));
std::copy(seq.begin(), seq.end(), d[0].begin());
for (int h = 1, half = 2; half < N; ++h, half <<= 1) {
for (int i = half; i < sz; i += half * 2) {
d[h][i - 1] = d[0][i - 1];
for (int j = i - 2; j >= i - half; --j) d[h][j] = op(d[0][j], d[h][j + 1]);
d[h][i] = d[0][i];
for (int j = i + 1; j < i + half; ++j) d[h][j] = op(d[h][j - 1], d[0][j]);
}
}
}
// [l, r), 0-indexed
S prod(int l, int r) const {
assert(l >= 0 and r <= N and l < r);
if (l + 1 == r) return d[0][l];
int h = _msb(l ^ (r - 1));
return op(d[h][l], d[h][r - 1]);
}
};
#line 3 "sparse_table/test/disjoint_sparse_table_rmq.test.cpp"
#include <iostream>
#line 5 "sparse_table/test/disjoint_sparse_table_rmq.test.cpp"
using namespace std;
int f(int l, int r) { return l < r ? l : r; };
int main() {
int N, Q;
cin >> N >> Q;
vector<int> A(N);
for (auto &x : A) cin >> x;
disj_sparse_table<int, f> rmq(A);
while (Q--) {
int l, r;
cin >> l >> r;
cout << rmq.prod(l, r) << '\n';
}
}