题意：有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
数据规模：
（1）矩阵中的所有数都不超过1,000,000,000
（2）20%的数据2<=a,b<=100,n<=a,n<=b,n<=10
（3）100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100
------------------------------------------------------------------我是分割线--------------------------------------------------------
题解：对于20%的数据，朴素做法是O（A*B）枚举每个边长为 N 的矩形，再O（N^2）求出矩形内最大值和最小值，取差值最小即可，总时间复杂度O（A*B*N^2）。
由于A*B的枚举矩形是最小下限，无法再优化，于是我们考虑优化求最值的 N^2 过程。
由题意，知道这种题的一般套路都是预处理。
对于以（i，j） 为左上角，长度为K的矩形，我们显然有以下的递推式：
Max(i，j，k) = max{Max(i，j，k)， Max(i-1，j-1，k-1)，Max(i，j-1，k-1)， Max(i-1，j，k-1) }
最小值同理。
由于空间限制，数组大小超内存限制，于是我们使用滚动数组优化，去掉K的一维，先预处理上边长为1的正方形，然后进行k-1次矩阵递推，得到的数据就一定是以k为边长的矩形的大小，总时间复杂度O（A*B*N），期望得分50分。
具体过程见代码实现：
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define rep(i, a, b) for(int i = (a);i <= (b);++i)
#define per(i, a, b) for(int i = (a);i >= (b);--i)
using namespace std;
typedef pair<int, int> pii;
typedef double db;
const int N = 1e6 + 50;
int a, b, n, Map[1010][1010];
int Max[1010][1010], Min[1010][1010];
int ans = 1e9;
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
while(ch >='0' && ch <='9'){x = (x<<3)+(x<<1)+(ch^48); ch = getchar();}
return x*f;
}
void init(){
a = read(); b = read(); n = read();
rep(i, 1, a) rep(j, 1, b){
Map[i][j] = read();
Max[i][j] = Min[i][j] = Map[i][j];
}
rep(k, 2, n) per(i, a, k) per(j, b, k){
Max[i][j] = max(max(Max[i-1][j-1], max(Max[i][j-1], Max[i-1][j])), Map[i][j]);
Min[i][j] = min(min(Min[i-1][j-1], min(Min[i][j-1], Min[i-1][j])), Map[i][j]);
}
}
void work(){
rep(i, n, a) rep(j, n, b) ans = min(ans, Max[i][j] - Min[i][j]);
printf("%d
", ans);
}
int main(){
init();
work();
return 0;
}
由于O（A*B*N）的时间复杂度并不够优秀，需要优化，而预处理复杂度已经达到下限，于是我们需要变换一下式子。
Max(i，j，k) = max{Max(i，j，k)， Max(i+2^(k-1)，j+2^(k-1)，k-1)，Max(i，j+2^(k-1)，k-1)， Max(i+2^(k-1)，j，k-1)) }
即用倍增的方法，发现这就是个二维ST表，预处理即可，总时间复杂度为O（A*BlogN）。
具体过程见代码实现：
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define rep(i, a, b) for(int i = (a);i <= (b);++i)
#define per(i, a, b) for(int i = (a);i >= (b);--i)
using namespace std;
typedef pair<int, int> pii;
typedef double db;
const int N = 1e6 + 50;
int a, b, n, Map[1010][1010];
int Max[1010][1010], Min[1010][1010];
int ans = 1e9;
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
while(ch >='0' && ch <='9'){x = (x<<3)+(x<<1)+(ch^48); ch = getchar();}
return x*f;
}
int ask_max(int l, int r){
int k = log2(n);
return max(Max[l][r], max(Max[l + n - (1<<k)][r + n - (1<<k)], max(Max[l + n - (1<<k)][r], Max[l][r + n - (1<<k)])));
}
int ask_min(int l, int r){
int k = log2(n);
return min(Min[l][r], min(Min[l + n - (1<<k)][r + n - (1<<k)], min(Min[l + n - (1<<k)][r], Min[l][r + n - (1<<k)])));
}
void init(){
a = read(); b = read(); n = read();
rep(i, 1, a) rep(j, 1, b){
Map[i][j] = read();
Max[i][j] = Min[i][j] = Map[i][j];
}
int t = log2(n);
rep(k, 0, t-1) rep(i, 1, a - (1<<k)) rep(j, 1, b - (1<<k)){
Max[i][j] = max(Max[i][j], max(Max[i + (1<<k)][j + (1<<k)], max(Max[i + (1<<k)][j], Max[i][j + (1<<k)])));
Min[i][j] = min(Min[i][j], min(Min[i + (1<<k)][j + (1<<k)], min(Min[i + (1<<k)][j], Min[i][j + (1<<k)])));
}
}
void work(){
rep(i, 1, a-n+1) rep(j, 1, b-n+1){
ans = min(ans, ask_max(i, j) - ask_min(i, j));
}
printf("%d
", ans);
}
int main(){
init();
work();
return 0;
}