训练4　二维区间最值差

题目描述（POJ2019）：约翰正在寻找最平坦的土地种植玉米。他花了很大的代价调查他的N×N公顷的方形农场（1≤N≤250）。每公顷都有一个整数高度（0≤高度≤250）。有K（1≤K≤100,000）组查询，整数B（1≤B≤N）是方形田地的一个边长，查询B×B子矩阵中最大高度和最小高度的差值。

输入：第1行包含3个整数N、B和K。第2..N+1行，每行都包含N个整数，代表N×N公顷每公顷的高度，每行的第1个整数都表示第1列，第2个整数都表示第2列。接下来K行，每行都包含两个整数（在1..N-B+1范围内），分别表示查询子矩阵左上角的行和列。

输出：对每个查询，都单行输出子矩阵中最大高度和最小高度的差值。

题解：本题属于二维区间最值查询问题，可以使用ST解决，只不过增加了一维，且查询时需要注意区间问题。Fmax[k][i][j]表示第k行[i, i+2j-1]区间的最大值，区间长度为2j。

1. 算法设计

（1）求出数据范围内所有数的log值，将其存储在数组lb[]中。

（2）将每个元素a[k][i]都存入F[k][i][0]中。

（3）创建二维ST。

（4）从当前位置(x, y)开始，向右B列，向下B行，查询每一行的最大值和最小值，再求区间最大值和最小值。输出二维区间的最大值和最小值之差。

2. 算法实现