题意
给定一个长度为 \(N\) 的数列，和 \(M\) 次询问，求出每一次询问的区间内数字的最大值。
对于 \(100\%\) 的数据，满足 \(1\le N\le {10}^5\)，\(1\le M\le 2\times{10}^6\)，\(a_i\in[0,{10}^9]\)，\(1\le l_i\le r_i\le N\)。
思路
什么是ST表
ST表，是一种用来处理RMQ（区间最值问题）的算法。ST表可以做到 \(\mathcal{O}(n\log{n})\) 预处理，之后 \(\mathcal{O}(1)\) 查询, ST表的空间复杂度也是 \(\mathcal{O}(n\log{n})\) 的。
如何实现ST表和它的原理
预处理
我们定义 \(ST_{i,j}\)，为从第 \(i\) 个位置开始之后的 \(2^j\) 个位置的区间最大值。 我们知道：\(2^k=2^{k-1}+2^{k-1}\)，所以在预处理时也一样。ST表有些类似于dp的思想。 \(ST_{i,j}=\max(ST_{i,j-1},ST_{i+2^{j-1},j-1})\)
\[\underbrace{i,i+1,i+2,\cdots,i+2^{j-1}-1}_{\text{max里的第一部分}}\underbrace{,i+2^{j-1},i+2^{j-1}+1,\cdots,i+2^{j-1}+2^{j-1}-1}_{\text{max里的第二部分}} \]这样就可以从小合大了。
查询
查询的话也很简单，求一下 \(k= \log{(r-l+1)}\)，也就是区间长度的覆盖。然后因为向下取整，不可以直接 \(ST_{l,k}\)，而是要用 \(r-2^k+1\) 重叠上去。不明白 \(r-2^k+1\)的话就是从终点开始往中心走那么多格子，这样的话一定可以和 \(ST_{l,k}\) 接上。
tips
需要注意一些边界，预处理的时候不要少处理，空间也要预留够。
代码
#include<cstdio>
#include <set>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
ll st[MAXN][40];
ll query(ll l,ll r){
ll k= ll(log2(r-l+1));
return max(st[l][k],st[r-(1<<k)+1][k]);
}
ll n,m,l,r;
int main(){
cin>>n>>m;
for (int i = 1; i <=n ; ++i) {
scanf("%lld",&st[i][0]);
}
for (int k = 1; k <=log2(MAXN) ; ++k) {
for (int i = 1; i+(1<<k)-1<=n ; ++i) {
st[i][k]= max(st[i][k-1],st[i+(1<<(k-1))][k-1]);
}
}
for (int i = 1; i <=m ; ++i) {
scanf("%lld%lld",&l,&r);
printf("%lld\n", query(l,r));
}
return 0;
}