回顾一下一些基础算法，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;
} |