题意：有n头牛，编号从1到n，每头牛的身高已知。现有q次询问，每次询问给出a，b两个数。要求给出编号在a与b之间牛身高的最大值与最小值之差。
思路：标准的RMQ问题。
RMQ问题是求给定区间内的最值问题。当询问量巨大时，最朴素算法必然超时。解决RMQ比较优秀的算法有ST算法。其预处理时间复杂度为O(nlogn)，询问的时间复杂度为O(1)。
ST的思想如下：
假设num数组中的数据从第0位开始存储。
用两个二维数组tmax，tmin分别求区间最大与最小值。ST的关键是数组区间的分割。tmax和tmin的下标是一致的，暂且拿tmax举例。
预处理：
预处理阶段运用的是DP的思想。tmax[i][j]内的值为区间[i, i + 2^j - 1]内的最大值。可以方便地理解为：第一个下标i为区间的开始位置，第二个坐标j表示区间的长度（只不过长度为指数形式）。如tmax[2][1]表示的是区间[2, 3]的最大值，tmax[2][2]表示的是区间[2, 5]的最大值。
而区间[i, i + 2^j - 1]可拆成[i, i + 2^(j - 1) - 1]和[i + 2^(j - 1), i + 2^j - 1]两个子区间。因此要计算tmax[i][j]的值，则有tmax[i][j] = max(tmax[i][j-1], tmax[i+2^(j-1)][j-1])。而所有递推的最初值tmax[i][0] = num[i]。对于tmin数组，下标的表示规则是相同的。
查询：
预处理进行完之后，可以进行查询。查询的复杂度为O(1)。
假设要查询区间[i, j]内的最大值。
首先第一步，先计算出一个整数k，k为满足表达式i + 2^k - 1 <= j 的最大整数。
然后将区间[i, j]分成两个部分重叠的子区间：[i, i + 2^k - 1]与[j - 2^k + 1, j]。
而tmax[i][k] 与tmax[j-2^k+1][k]中在预处理阶段便已计算出了结果，此时只需要输出两者中的较大者即可。
其他细节请看代码。
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define maxn 50020
using namespace std; int cow[maxn], tmax[maxn][], tmin[maxn][];
void st(int n)
{
int k = (int)(log((double)n) / log(2.0));
for (int i = ; i < n; i++)
tmin[i][] = tmax[i][] = cow[i];//递推的初值
for (int j = ; j <= k; j++)
for (int i = ; i + ( << j) - < n; i++)
{
int m = i + ( << (j - ));//求出中间值
tmax[i][j] = max(tmax[i][j-], tmax[m][j-]);
tmin[i][j] = min(tmin[i][j-], tmin[m][j-]);
}
}
//查询i和j之间的最值，注意i是从0开始的
void rmq(int i, int j)
{
int k = (int)(log(double(j - i + )) / log(2.0));
int t1 = max(tmax[i][k], tmax[j-(<<k)+][k]);
int t2 = min(tmin[i][k], tmin[j-(<<k)+][k]);
printf("%d\n",t1 - t2);
}
int main()
{
int n, q;
//freopen("data.in", "r", stdin);
scanf("%d%d",&n,&q);
for (int i = ; i < n; i++) scanf("%d",&cow[i]);
st(n);
while (q--)
{
int a, b;
scanf("%d%d",&a,&b);
rmq(a - , b - );//st算法从第0位开始，因此需要减一
}
return ;
}