最简单的RMQ问题，这次改用ST算法来写，存下来当模板吧。
ST算法通过nlogn的时间（也可以是O(n)）预处理出d[i][j]（起始位置为i长度为2^(j-1))区间的内的最值,递推式：d[i][j] = min(d[i][j-1],d[I+2^(j-1][j-1])
查询的时候先找到一个k有2^(k+1)>(R-L+1)然后可得minv(L,R)=min(d[L][K],d[R-(1<<K)+1][k])中间有些元素可能重复判断了，不过求最值问题不需要考虑这些。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>using
namespace
std;
const
int
maxn = 50001;
int
minv[maxn][20],maxv[maxn][20],n,val[maxn],q;
void
init_RMQ() {
for
(int
i = 0; i < n; i++) minv[i][0] = maxv[i][0] = val[i];
for
(int
j = 1; (1 << j) <= n; j++) {
for
(int
i = 0; i + (1 << j) < n + 1; i++) {
maxv[i][j] = max(maxv[i][j - 1], maxv[i + (1 << (j - 1))][j - 1]);
minv[i][j] = min(minv[i][j - 1], minv[i + (1 << (j - 1))][j - 1]);
}
}
}int
main() {
scanf("%d%d", &n, &q);
for
(int
i = 0; i < n; i++) scanf("%d", val + i);
init_RMQ();
int
a, b;
for
(int
i = 0; i < q; i++) {
scanf("%d%d", &a, &b); a--; b--;
int
k = 0;
while
((1 << (k + 1)) <= b - a + 1) k++;
printf("%d\n", max(maxv[a][k], maxv[b - (1 << k) + 1][k]) - min(minv[a][k], minv[b - (1 << k) + 1][k]));
}
return
0;
} |