Balanced Lineup

For the daily milking, Farmer John‘s N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

6 31734251 54 62 2

630

///RMQ问题之Sparse_Table算法  模板 区间最大最小值#include <math.h>#include <stdio.h>#include <iostream>#define max(a,b) a>b?a:b#define min(a,b) a<b?a:busing namespace std;const int N=100005;int n,Q,c[N],a,b;int dp_max[N][33];  ///33足够用 2^32 是 intint dp_min[N][33];void Init(){    for(int i=1; i<=n; i++)        dp_max[i][0] = dp_min[i][0] = c[i];    double limit = log(n)/log(2.0);    for(int j=1; j<=(int)limit; j++)        for(int i=1; i+(1<<j)-1<=n; i++)        {            dp_max[i][j] = max(dp_max[i][j-1],dp_max[i+(1<<(j-1))][j-1]);            dp_min[i][j] = min(dp_min[i][j-1],dp_min[i+(1<<(j-1))][j-1]);        }}int Get_Max(int a,int b){    int k = (int)(log(b-a+1)/log(2.0));    return max(dp_max[a][k],dp_max[b-(1<<k)+1][k]);}int Get_Min(int a,int b){    int k = (int)(log(b-a+1)/log(2.0));    return min(dp_min[a][k],dp_min[b-(1<<k)+1][k]);}int main(){    scanf("%d%d",&n,&Q);    for(int i=1; i<=n; i++)        scanf("%d",&c[i]);    Init();    while(Q--)    {        scanf("%d%d",&a,&b);        printf("%d\n",Get_Max(a,b)-Get_Min(a,b));    }    return 0;}

RMQ问题，全名(Range Minimum/Maximum Query)，是求给定区间中的最值问题。

主要方法及复杂度如下：

1、朴素（即搜索），O(n)-O(qn) online。

2、线段树，O(n)-O(qlogn) online。

3、Sparse_Table（实质是动态规划），O(nlogn)-O(1) online。

4、RMQ标准算法：先规约成LCA（Lowest Common Ancestor），再规约成约束RMQ，O(n)-O(1) online。

ST算法可以在O(nlogn)的预处理以后实现O(1)的查询效率，从而解决查询次数很多（如大于100万）的RMQ问题。

首先，是预处理。预处理是采用dp的思想，我们用f[i][j]表示区间[i,i+2^j-1]中的最大值（即从i开始，长度为2^j的闭区间）。

开始时，f[i][0]一定等于num[i]。好了，初始值找到了，下面是状态转移方程：

f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])。即把[i,i+2^j-1]区间分成两部分[i,i+2^(j-1)-1]和[i+2^(j-1),i+2^(j-1)+2^(j-1)-1]，正好和原区间一致。

有了初始值和转移方程，我们可以自底向上递推出所有的f[i][j]的值。

对于边界，还要注意一点。由于区间长度最大为n，所以二维边界最大为log(n)/log(2.0);

一维边界只要满足对于每个起始点，都可以有长度找到n就行了，也就是让i+2^j-1<=n就好了。

然后就是查询了。假设要查询区间[a,b]的最大值，由于区间的长度很可能不是2的整数幂，所以我们要把区间划分为长度为2的整数幂的两部分，而且这两个区间的并集必须是[a,b]。为了实现这个方案，我们需要先求出一个最大的k，使得2^k<=(b-a+1)，这样就可以把区间分成两部分[a,a+2^k-1]和[b-2^k+1,b]，使他们既能不超过a,b区间的范围，又能把区间全部覆盖。于是，[a,b]区间的最大值就等于上述两个区间的最大值中最大的那个。(有点绕)