最简单的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;} |
POJ 3264 Balanced Lineup (RMQ问题)
原文：http://www.cnblogs.com/rolight/p/3530053.html