好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

题目描述

原题来自 USACO 2007 Jan. Gold

FJ 的 $N$ 头牛总是按同一序列排队。有一天，FJ 决定让一些牛玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛，但是为了避免水平悬殊，牛的身高不应该相差太大。FJ 准备了 $Q$ 个可能的牛的选择和所有牛的身高。他想知道每一组里面最高和最低的牛的身高差别。

输入格式

第一行：两个整数 $N$ 和 $Q$；

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

第 $N+2$ 至第 $N+Q+1$ 行：每行两个整数 $A$ 和 $B$，表示询问区间 $[A, B]$ 内最高和最矮牛的身高差。

输出格式

输出 $Q$ 行，每行一个整数，表示对应询问的答案（最高身高减去最低身高）。

样例

样例输入

6 3
1
7
3
4
2
5
1 5
4 6
2 2

样例输出

6
3
0

样例说明

牛的身高：$[1, 7, 3, 4, 2, 5]$。

询问1：区间 $[1,5]$ → 身高 $1,7,3,4,2$，最高 $7$，最低 $1$，差 $6$。
询问2：区间 $[4,6]$ → 身高 $4,2,5$，最高 $5$，最低 $2$，差 $3$。
询问3：区间 $[2,2]$ → 身高 $7$，最高最低相同，差 $0$。

数据范围

对于全部数据：

• $1 \le N \le 5\times 10^4$
• $1 \le Q \le 1.8\times 10^5$
• $1 \le h_i \le 10^6$
• $1 \le A \le B \le N$

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$（512 MB）

提示
此题为 静态区间最大值最小值查询 问题，即 RMQ 与 区间最小值查询 的结合。

由于 $N$ 不大（$5\times 10^4$），$Q$ 较大（$1.8\times 10^5$），我们需要 $O(1)$ 或 $O(\log N)$ 的查询。

方法一：两个 ST 表

• 一个 ST 表维护区间最大值；
• 另一个 ST 表维护区间最小值；
• 查询时分别得到最大值和最小值，相减即可。

复杂度：预处理 $O(N \log N)$，查询 $O(1)$，总复杂度 $O(N \log N + Q)$。

方法二：线段树

• 线段树节点同时维护区间最大值和最小值；
• 查询时递归合并。

复杂度：预处理 $O(N)$，查询 $O(\log N)$，总复杂度 $O(N + Q \log N)$，在 $Q$ 较大时可能略慢于 ST 表。

推荐方法：使用 两个 ST 表，查询更快。

ST 表实现：

1. 预处理 $\log_2$ 表；
2. 建立 $fmax[i][j]$ 和 $fmin[i][j]$，分别表示区间 $[i, i+2^j-1]$ 的最大值和最小值；
3. 初始化 $fmax[i][0] = fmin[i][0] = h[i]$；
4. 递推：
   • $fmax[i][j] = \max(fmax[i][j-1], fmax[i+2^{j-1}][j-1])$；
   • $fmin[i][j] = \min(fmin[i][j-1], fmin[i+2^{j-1}][j-1])$；
5. 查询 $[l, r]$：
   • $k = \lfloor \log_2(r-l+1) \rfloor$；
   • $maxv = \max(fmax[l][k], fmax[r-2^k+1][k])$；
   • $minv = \min(fmin[l][k], fmin[r-2^k+1][k])$；
   • 输出 $maxv - minv$。

注意：

• $N=5\times 10^4$，$\log_2 N \approx 16$，ST 表大小 $N \times 17$ 约 $8.5\times 10^5$ 个整数，两个表约 $1.7\times 10^6$ 个整数，内存约 $6.8$ MB，可以接受；
• 输入输出量大，建议使用快速 IO。