```cpp
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define size_t int
template <typename _Tp, size_t _MAXN>
class normal_sparse_table {
_Tp (*_M_func)(const _Tp&, const _Tp&);
static constexpr size_t _S_size = std::__lg(_MAXN);
_Tp _M_table[_S_size + 1][_MAXN];
inline void init() { for (size_t j = 1; j < _S_size; j++) for (size_t i = 0; i <= _MAXN - (1 << j); i++) _M_table[j][i] = _M_func(_M_table[j - 1][i], _M_table[j - 1][i + (1 << (j - 1))]); }
public:
normal_sparse_table() = default;
template <typename _InputIterator>
normal_sparse_table(_InputIterator __first, _InputIterator __last, _Tp (*func)(const _Tp&, const _Tp&)) : _M_func(func) {
std::copy(__first, __last, _M_table[0]);
init();
}
normal_sparse_table<_Tp, _MAXN>& operator=(const normal_sparse_table<_Tp, _MAXN>& o) {
for (size_t i = 0; i < _S_size; i++) memcpy(_M_table[i], o._M_table[i], _MAXN * sizeof(_Tp));
_M_func = o._M_func;
return *this;
}
// query [l,r]
inline _Tp query(size_t l, size_t r) {
size_t k = std::__lg(r - l + 1);
return _M_func(_M_table[k][l], _M_table[k][r - (1 << k) + 1]);
}
};
template <typename _Tp, size_t _MAXN>
class sparse_table {
_Tp(*_M_func)(const _Tp&, const _Tp&);
static constexpr size_t _S_blk_siz = std::__lg(_MAXN);
static constexpr size_t _S_blk_cnt = _MAXN / _S_blk_siz + 5;
_Tp _M_pre[_S_blk_cnt * _S_blk_siz], _M_suf[_S_blk_cnt * _S_blk_siz], _M_arr[_MAXN];
normal_sparse_table<_Tp, _S_blk_cnt> _M_st_table;
inline void init() {
std::fill(std::copy(_M_arr, _M_arr + _MAXN, _M_pre), _M_pre + _S_blk_cnt * _S_blk_siz, _Tp());
std::fill(std::copy(_M_arr, _M_arr + _MAXN, _M_suf), _M_suf + _S_blk_cnt * _S_blk_siz, _Tp());
_Tp *tmp_arr = new _Tp[_S_blk_cnt + 1];
size_t curpos = 0;
for (size_t bl = 0, br = _S_blk_siz - 1; bl < _MAXN; bl += _S_blk_siz, br += _S_blk_siz) {
br = std::min(br, _MAXN);
for (size_t k = bl + 1; k < br; k++) _M_pre[k] = _M_func(_M_pre[k - 1], _M_pre[k]);
for (size_t k = br - 1; k >= bl; k--) _M_suf[k] = _M_func(_M_suf[k + 1], _M_suf[k]);
tmp_arr[curpos++] = _M_suf[bl];
}
_M_st_table = normal_sparse_table<_Tp, _S_blk_cnt>(tmp_arr, tmp_arr + curpos, _M_func);
}
public:
template <typename _InputIterator>
sparse_table(_InputIterator __first, _InputIterator __last, _Tp(*func)(const _Tp&, const _Tp&)) : _M_func(func) {
std::copy(__first, __last, _M_arr);
init();
}
// query [l,r]
_Tp query(size_t l, size_t r) {
size_t bl = l / _S_blk_siz, br = r / _S_blk_siz;
_Tp ret{};
if (bl == br) {
for (size_t i = l; i <= r; i++) ret = _M_func(ret, _M_arr[i]);
return ret;
}
if (bl == br - 1) return _M_func(_M_suf[l], _M_pre[r]);
return _M_func(_M_func(_M_suf[l], _M_pre[r]), _M_st_table.query(bl + 1, br - 1));
}
};
inline int my_max(const int& a, const int& b) { return std::max(a, b); }
int arr[150005];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) scanf("%d", arr + i);
sparse_table<int, 150005> table(arr, arr + n, my_max);
while (m--) {
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", table.query(l - 1, r - 1));
}
}
```
by Ruiqun2009 @ 2023-01-16 16:07:57
lz 贴错代码了吧
by lazytag @ 2023-01-16 20:49:18
@[lazytag](/user/137176) 没有啊，这就是线性 RMQ 的代码啊
by Ruiqun2009 @ 2023-01-17 13:11:12
@[Ruiqun2009](/user/589895) 预处理不就是 nlogn 了吗？还是说我看错了吗？
by lazytag @ 2023-01-17 13:54:52
@[Ruiqun2009](/user/589895) 算了，大概是我错了，不要在意。
by lazytag @ 2023-01-17 13:55:41
@[lazytag](/user/137176) 那是普通 RMQ，我这是线性做法
by Ruiqun2009 @ 2023-01-17 13:55:55
已过
原因：44 行边界条件应为 $\leq br$
此贴结
by Ruiqun2009 @ 2023-01-18 20:15:38