奶牛排队（RMQ）

每天，农夫 John 的 $N$ 头牛总是按同一序列排队。

有一天，John 决定让一些牛玩一场飞盘比赛。

他准备找一群在队列中位置连续的牛来进行比赛，但是为了避免水平悬殊，牛的身高不应该相差太大。

John 准备了 $Q$ 个可能的牛的选择和所有牛的身高。

他想知道每一组里面最高和最矮的牛的身高差别。

输入格式

第一行包含两个整数 $N,Q$。

第二至第 $N+1$ 行，第 $i$ 行是第 $i$ 头牛的身高 $h_i$；

第 $N+2$ 至第 $N+Q+1$ 行，每行两个整数 $A$ 和 $B$，表示从 $A$ 到 $B$ 的所有牛。

牛的编号从 $1$ 到 $N$。

输出格式

第一至第 $Q$ 行，每行一个整数，表示对于询问的回答（即最高和最矮的牛的身高差）。

数据范围

$1≤N≤5×10^4$ ,
$ 1 ≤ Q ≤ 1.8×10^5 $,
$1 ≤ h_i ≤ 10^6$,
$1≤A≤B≤N$

思路：

对于每一个询问都进行线性扫描的总时间复杂度是 $O(Q \times (r - l + 1)) = 5×10^4 × 1.8×10^5 = 9×10^9$，肯定是超时的。这里需要使用RMQ(Range Minimum/Maximum Query)算法优化。

RMQ 预处理

首先，使用$ dp[i][j] $ 表示从 $i$ 开始连续 $2^j$ 个数中的最小（最大）值。

$ dp[i][j] $ 又可以被拆分成两部分，分别为：$[i, i + 2^{j - 1} - 1]$ 和 $[i + 2^{j - 1}, i + 2^j - 1]$

因此有状态转移方程: $dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1])$

类似于区间 $DP$ ，该状态转移方程在循环时，外层应为 $j$ （长度），内层为区间起点 $i$ 。

RMQ 算法预处理的时间复杂度为 $O(nlogn)$。

RMQ 查询

查询时，根据 $dp[i][j]$ 的定义以及根据区间长度得到的 $ t = {\log_2}(r - l + 1)$ （下取整），有：

$ res_{max} = max(dp[l][t], dp[r - (1 << t) + 1][t]) $,

$ res_{min} = min(dp[l][t], dp[r - (1 << t) + 1][t]) $

分析一下，$2 \times 2^t \le r - l + 1$，因此上述公式中虽有重复覆盖的部分，但是不影响区间最值的求取，且一定在 $[l, r]$ 区间内。

RMQ 算法查询的时间复杂度为 $O(1)$。

时间复杂度

预处理 $\log_2(x)$ 的时间复杂度为 $O(n)$，RMQ 算法预处理的时间复杂度为 $O(nlogn)$，$n$ 次查询的时间复杂度为 $O(n)$，因此总时间复杂度是 $O(nlogn)$ 。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 5e4 + 10, K = 16;
int h[N], maxh[N][K], minh[N][K], mylog[N];

int main()
{
    int n, q, l, r;
    scanf("%d%d", &n, &q);
    for(int i = 2; i <= n; ++i)
        mylog[i] = mylog[i / 2] + 1;
    for(int i = 1; i <= n; ++i)
        scanf("%d", &h[i]), maxh[i][0] = minh[i][0] = h[i];
    for(int j = 1; (1 << j) <= n; ++j)
        for(int i = 1; i + (1 << j) - 1 <= n; ++i)
        {
            maxh[i][j] = max(maxh[i][j - 1], maxh[i + (1 << (j - 1))][j - 1]);
            minh[i][j] = min(minh[i][j - 1], minh[i + (1 << (j - 1))][j - 1]);
        }
    while(q--)
    {
        scanf("%d%d", &l, &r);
        int t = mylog[r - l + 1];
        int res_max = max(maxh[l][t], maxh[r - (1 << t) + 1][t]);
        int res_min = min(minh[l][t], minh[r - (1 << t) + 1][t]);
        printf("%d\n", res_max - res_min);
    }
    return 0;
}