Introduce
时间复杂度:O(nloglogn) ~ O(1)
空间复杂度:O(nloglogn)
Code
template <typename T,
class Cmp = std::less<T>
>
class RMQ {
private:
static constexpr unsigned B = 64;
const Cmp cmp = Cmp();
const int n;
std::vector<uint64_t> stk;
std::vector<T> ini, pre, suf;
std::vector<std::vector<T>> a;
public:
explicit RMQ(const std::vector<T> &v): n(v.size()), stk(n) {
ini = pre = suf = v;
const int M = (n - 1) / B + 1;
const int lg = std::__lg(M);
a.assign(lg + 1, std::vector<T>(M));
for (int i = 0; i < M; i++) {
a[0][i] = v[i * B];
for (int j = 1; j < B && i * B + j < n; j++) {
a[0][i] = std::min(a[0][i], v[i * B + j], cmp);
}
}
for (int j = 0; j < lg; j++) {
for (int i = 0; i + (2 << j) <= M; i++) {
a[j + 1][i] = std::min(a[j][i], a[j][i + (1 << j)], cmp);
}
}
for (int i = 1; i < n; i++) {
if (i % B) {
pre[i] = std::min(pre[i - 1], pre[i], cmp);
}
}
for (int i = n - 2; i >= 0; i--) {
if (i % B != B - 1) {
suf[i] = std::min(suf[i], suf[i + 1], cmp);
}
}
for (int i = 0; i < M; i++) {
const int l = i * B;
const int r = std::min<uint64_t>(n, l + B);
uint64_t s = 0;
for (int j = l; j < r; j++) {
while (s && cmp(v[j], v[std::__lg(s) + l])) {
s ^= 1ULL << std::__lg(s);
}
s |= 1ULL << (j - l);
stk[j] = s;
}
}
}
T operator() (int l, int r) const {
if (l / B != (r - 1) / B) {
T ans = std::min(suf[l], pre[r - 1], cmp);
l = l / B + 1;
r = r / B;
if (l < r) {
int k = std::__lg(r - l);
ans = std::min({ans, a[k][l], a[k][r - (1 << k)]}, cmp);
}
return ans;
} else {
int x = (l / B) * B;
return ini[__builtin_ctzll(stk[r - 1] >> (l - x)) + l];
}
}
};
Usage
天才的记忆
#include <bits/stdc++.h>
...
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
RMQ<int, std::greater<int>> rmq(a);
int m;
std::cin >> m;
while (m --) {
int l, r;
std::cin >> l >> r;
l--;
std::cout << rmq(l, r) << "\n";
}
return 0;
}