3264
-- Balanced Lineup
很裸的一道RMQ題目，開始不知道Sparse Table怎么寫，后面問了之后才知道是用二進制的思想，用DP的方法的方法求出。
Sparse Table其實就相當于一個高效的打表方法（算法時間&&空間復雜度為O(nlogn)），我們設f(i, j)表示[i, i+2j-1]區間中的最小值，即
f(0, 0)表示[0, 0]中的最小值
f(0,
2)表示[0, 3]中的最小值
f(2,
4)表示[2, 17(2+16-1)]中的最小值
………………
在做最值的稀疏表（Sparse Table）時，因為是自頂向下推理，要注意循環嵌套的順序
其中j從0→log2(n) //j = 0 的情況，將f(i, 0) 初始化為 d[i]
i從0→i+2j-1
< n
求最值f[i][j]：具體參考程序
打完了Sparse Table之后，假設我們要找[a, b]區間中的最小值，則我們
1先求出一個最大的k，使得(b – a +1) > 2k
這樣就能把[a, b]分成兩個（部分重疊的）長度為2k的空間
2所以要求[a, b]的最小值，只需返回（因為前面求了的）[m, m+2k-1]和[n-2k+1, n]中的最小值即可，算法復雜度為O(n)。
對于i從0開始還是從1開始，其實這個無所謂，從0開始的話，只需將每個question中的位置-1即可，而且跟符合C中編程思想一些。
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
#define maxs(a, b) ((a>b)?(a):(b))
#define mins(a, b) ((a<b)?(a):(b))
const int MAXN = 50010;
int d[MAXN];
int dpmin[MAXN][17];
int dpmax[MAXN][17]; //2^16 = 65536 > 50000
int n, q;
void createDpmin() {
int
i, j, k;
//
initial situation: j = 0;
for
(i = 0; i < n; i++)
dpmin[i][0]
= d[i]; //遞推的初值：一個數的最值肯定是自己
//bottom-top
approach: so j is in the outer loop
for (j = 1; j <=
log((double)(n))/log(2.0); j++){
for (i = 0;
i+(1<<j)-1 < n; i++) {
dpmin[i][j]
= mins(dpmin[i][j-1], dpmin[i+(1<<(j-1))][j-1]);
}
}
}
void createDpmax() {
int
i, j;
for
(i = 0; i < n; i++)
dpmax[i][0]
= d[i];
for
(j = 1; j <= log((double)(n))/log(2.0); j++) {
for
(i = 0; i+(1<<j)-1 < n; i++) {
dpmax[i][j]
= maxs(dpmax[i][j-1], dpmax[i+(1<<(j-1))][j-1]);
}
}
}
void initi() {
createDpmin();
createDpmax();
//dump(n);
}
int rminq(int a, int b) {
int
k = (int)(log((double)(b - a + 1))/log(2.0));
return
mins(dpmin[a][k], dpmin[b-(1<<k)+1][k]);
}
int rmaxq(int a, int b) {
int
k = (int)(log((double)(b - a + 1))/log(2.0));
return
maxs(dpmax[a][k], dpmax[b-(1<<k)+1][k]);
}
int main() {
int
i;
int
a, b;
int
ans;
while
(scanf("%d %d", &n, &q) != EOF) {
for
(i = 0; i < n; i++)
scanf("%d",
&d[i]);
initi();
while(q--)
{
scanf("%d
%d", &a, &b);
ans
= rmaxq(a-1, b-1) - rminq(a-1, b-1);
printf("%d\n",
ans);
}
}
return
0;
}