基于状压的线性 RMQ 算法
严格 \(\mathcal O(N)\) 预处理，\(\mathcal O(1)\) 查询。
template<class T, class Cmp = less<T>> struct RMQ {const Cmp cmp = Cmp();static constexpr unsigned B = 64;using u64 = unsigned long long;int n;vector<vector<T>> a;vector<T> pre, suf, ini;vector<u64> stk;RMQ() {}RMQ(const vector<T> &v) {init(v);}void init(const vector<T> &v) {n = v.size();pre = suf = ini = v;stk.resize(n);if (!n) {return;}const int M = (n - 1) / B + 1;const int lg = __lg(M);a.assign(lg + 1, 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] = min(a[0][i], v[i * B + j], cmp);}}for (int i = 1; i < n; i++) {if (i % B) {pre[i] = min(pre[i], pre[i - 1], cmp);}}for (int i = n - 2; i >= 0; i--) {if (i % B != B - 1) {suf[i] = min(suf[i], suf[i + 1], cmp);}}for (int j = 0; j < lg; j++) {for (int i = 0; i + (2 << j) <= M; i++) {a[j + 1][i] = min(a[j][i], a[j][i + (1 << j)], cmp);}}for (int i = 0; i < M; i++) {const int l = i * B;const int r = min(1U * n, l + B);u64 s = 0;for (int j = l; j < r; j++) {while (s && cmp(v[j], v[__lg(s) + l])) {s ^= 1ULL << __lg(s);}s |= 1ULL << (j - l);stk[j] = s;}}}T operator()(int l, int r) {if (l / B != (r - 1) / B) {T ans = min(suf[l], pre[r - 1], cmp);l = l / B + 1;r = r / B;if (l < r) {int k = __lg(r - l);ans = min({ans, a[k][l], a[k][r - (1 << k)]}, cmp);}return ans;} else {int x = B * (l / B);return ini[__builtin_ctzll(stk[r - 1] >> (l - x)) + l];}}
};