这题一种做法是单调队列，像二维的滑动窗口。或是二维st表。我用的是第二种方法。
首先预处理的时候，对于一个边长为2k的正方形的最大值（最小值同理），应该由位于这个正方形的四个角上的边长为2k-1的小正方形转化而来。令Maxi,j,k表示左上角为(i, j) 的边长为2k的正方形的最大值，则
Maxi,j,k = max(Maxi,j,k - 1, Maxi,j + (1 << (k - 1)),k - 1, Maxi + (1 << (k - 1)),j,k - 1, Maxi + (1 << (k - 1)),j + (1 << (k - 1)),k - 1);
查询的时候，我们先求一个值kn，表示在2k <= n的前提下k的最大值。求完这个就像一维st表那样，只不过从这个n * n的正方形的四个角所在的小正方形转化而来，如下图
这个n * n的正方形的最大值就由这四个小正方形最大值转化而来。
这样转移方程就出来了
maxx = max(Maxi,j,kn, Maxi,j + n - (1 << kn),kn, Maxi + n - (1 << kn),j,kn, Maxi + n - (1 << kn),j + n - (1 << kn),kn)
有一个小优化就是预处理的时候k只用枚举到kn，而不是到(1 << k) == min(a, b).
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<cstdlib> 7 #include<stack> 8 #include<queue> 9 #include<vector> 10 #include<cctype> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a) memset(a, 0, sizeof(a)) 15 typedef long long ll; 16 typedef double db; 17 const int INF = 0x3f3f3f3f; 18 const db eps = 1e-8; 19 const int maxn = 1e3 + 5; 20 inline ll read() 21 { 22 ll ans = 0; 23 char ch = getchar(), last = ' '; 24 while(!isdigit(ch)) {last = ch; ch = getchar();} 25 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 26 if(last == '-') ans = -ans; 27 return ans; 28 } 29 inline void write(ll x) 30 { 31 if(x < 0) putchar('-'), x = -x; 32 if(x >= 10) write(x / 10); 33 putchar(x % 10 + '0'); 34 } 35 36 int x, y, n, a[maxn][maxn]; 37 38 int Max[maxn][maxn][7], Min[maxn][maxn][7], nk; 39 void rmq() 40 { 41 for(int i = 1; i <= x; ++i) 42 for(int j = 1; j <= y; ++j) Max[i][j][0] = Min[i][j][0] = a[i][j]; 43 for(int k = 1; (1 << k) <= n; ++k) 44 for(int i = 1; i + (1 << k) - 1 <= x; ++i) 45 for(int j = 1; j + (1 << k) - 1 <= y; ++j) 46 { 47 Max[i][j][k] = max(max(Max[i][j][k - 1], Max[i][j + (1 << (k - 1))][k - 1]), max(Max[i + (1 << (k - 1))][j][k - 1], Max[i + (1 << (k - 1))][j + (1 << (k - 1))][k - 1])); 48 Min[i][j][k] = min(min(Min[i][j][k - 1], Min[i][j + (1 << (k - 1))][k - 1]), min(Min[i + (1 << (k - 1))][j][k - 1], Min[i + (1 << (k - 1))][j + (1 << (k - 1))][k - 1])); 49 } 50 while((1 << (nk + 1)) <= n) nk++; 51 } 52 53 int ans = 2147483647; 54 55 int main() 56 { 57 x = read(); y = read(); n = read(); 58 for(int i = 1; i <= x; ++i) 59 for(int j = 1; j <= y; ++j) a[i][j] = read(); 60 rmq(); 61 for(int i = 1; i <= x - n + 1; ++i) 62 for(int j = 1; j <= y - n + 1; ++j) 63 { 64 int _max = max(max(Max[i][j][nk], Max[i][j + n - (1 << nk)][nk]), max(Max[i + n - (1 << nk)][j][nk], Max[i + n - (1 << nk)][j + n - (1 << nk)][nk])); 65 int _min = min(min(Min[i][j][nk], Min[i][j + n - (1 << nk)][nk]), min(Min[i + n - (1 << nk)][j][nk], Min[i + n - (1 << nk)][j + n - (1 << nk)][nk])); 66 ans = min(ans, _max - _min); 67 } 68 write(ans); enter; 69 return 0; 70 }