回顾一下一些基础算法，Sparse Table有种dp的感觉，写起来有点棘手吧，主要是因为下标的问题，贴一记代码，等下写一个非递归的线段树试试。
|
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
30
31
32
33
34
35
36
37
38
39 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cstdio>#include<vector>#include<cmath>#define maxn 50000#define max_logn 20using
namespace std;int
dmin[maxn+20][max_logn];int
dmax[maxn+20][max_logn];int
a[maxn+50];int
n,m;int
main(){ while
(cin >> n>>m) { for
(int i = 1; i <= n; i++) scanf("%d", a + i); for
(int i = 1; i <= n; i++) dmin[i][0] =dmax[i][0] = a[i]; for
(int j = 1; (1<<j) <= n; j++){ for
(int i = 0; i+(1<<j)-1 <= n; i++){ dmin[i][j] = min(dmin[i][j - 1], dmin[i + (1<<(j-1))][j - 1]); dmax[i][j] = max(dmax[i][j - 1], dmax[i + (1<<(j-1))][j - 1]); } } int
l, r; for
(int i = 0; i < m; i++){ scanf("%d%d", &l, &r); int
k = 0; int
len = r - l + 1; while
((1 << (k+1)) < len) k++; printf("%d\n", max(dmax[l][k],dmax[r-(1<<k)+1][k])-min(dmin[l][k], dmin[r - (1 << k) + 1][k])); } } return
0;} |
原文：http://www.cnblogs.com/chanme/p/3537418.html