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)时,因为是自顶向下推理,要注意循环嵌套的顺序

其中j0log2(n)                            //j = 0 的情况,将f(i, 0) 初始化为 d[i]

         i0i+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)

 

对于i0开始还是从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;

}