二维st表秒了，这题纯送

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
bool Test_MLE_start;
constexpr int N=1005;
int _=1,n,m,k,ans=2e9,a[N][N],maxn[N][N][15],minn[N][N][15];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("square.in","r",stdin);
	freopen("square.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
int asksmaxn(int x1,int y1,int x2,int y2){
	int k=log(x2-x1+1)/log(2);
	return max(max(maxn[x1][y1][k],maxn[x2-(1<<k)+1][y1][k]),max(maxn[x1][y2-(1<<k)+1][k],maxn[x2-(1<<k)+1][y2-(1<<k)+1][k]));
}int asksminn(int x1,int y1,int x2,int y2){
	int k=log(x2-x1+1)/log(2);
	return min(min(minn[x1][y1][k],minn[x2-(1<<k)+1][y1][k]),min(minn[x1][y2-(1<<k)+1][k],minn[x2-(1<<k)+1][y2-(1<<k)+1][k]));
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m=reads(),k=reads();
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++) minn[i][j][0]=maxn[i][j][0]=a[i][j]=reads();
		}for(int k=1;k<=14;k++){
			for(int i=1;i+(1<<k)-1<=n;i++){
				for(int j=1;j+(1<<k)-1<=m;j++){
					maxn[i][j][k]=max(max(maxn[i][j][k-1],maxn[i][j+(1<<(k-1))][k-1]),max(maxn[i+(1<<(k-1))][j][k-1],maxn[i+(1<<(k-1))][j+(1<<(k-1))][k-1]));
					minn[i][j][k]=min(min(minn[i][j][k-1],minn[i][j+(1<<(k-1))][k-1]),min(minn[i+(1<<(k-1))][j][k-1],minn[i+(1<<(k-1))][j+(1<<(k-1))][k-1]));
				}
			}
		}for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(i+k-1>n||j+k-1>m) continue;
				int x1=i,y1=j,x2=i+k-1,y2=j+k-1;
				ans=min(asksmaxn(x1,y1,x2,y2)-asksminn(x1,y1,x2,y2),ans);
			}
		}printf("%d\n",ans);
	}
	return 0;
}
/*
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
*/

$\mathcal O(ab)$ 做法。

使用单调队列维护每一行连续 $n$ 个的最值。然后再开一个列的单调队列，这样就获得了矩阵的最值。

然后写四堵墙就行了，挺好调的5min就调完了。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x*y;
}
const int N=2005;
int n,m,k,a[N][N];
int s[2][N][N],f[2][N][N],q[N];
signed main() {
	R(n),R(m),R(k);
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) R(a[i][j]);
	memset(s[0],0x3f,sizeof s[0]);
	memset(f[0],0x3f,sizeof f[0]);
	for(int i=1,l=1,r=0; i<=n; ++i) {
		for(int j=1; j<=k; ++j) {
			while(l<=r&&a[i][j]<=a[i][q[r]])--r;
			q[++r]=j,s[0][i][1]=min(s[0][i][1],a[i][j]);
		}
		for(int j=k+1; j<=m; ++j) {
			while(l<=r&&j-q[l]+1>k)++l;
			if(l<=r) s[0][i][j-k+1]=a[i][q[l]];
			s[0][i][j-k+1]=min(s[0][i][j-k+1],a[i][j]);
			while(l<=r&&a[i][j]<=a[i][q[r]])--r;
			q[++r]=j;
		}
	}
	
	for(int i=1,l=1,r=0; i<=n; ++i) {
		for(int j=1; j<=k; ++j) {
			while(l<=r&&a[i][j]>=a[i][q[r]])--r;
			q[++r]=j,s[1][i][1]=max(s[1][i][1],a[i][j]);
		}
		for(int j=k+1; j<=m; ++j) {
			while(l<=r&&j-q[l]+1>k)++l;
			if(l<=r) s[1][i][j-k+1]=a[i][q[l]];
			s[1][i][j-k+1]=max(s[1][i][j-k+1],a[i][j]);
			while(l<=r&&a[i][j]>=a[i][q[r]])--r;
			q[++r]=j;
		}
	}
	
	for(int j=1,l=1,r=0; j<=m; ++j) {
		for(int i=1; i<=k; ++i) {
			while(l<=r&&s[0][i][j]<=s[0][q[r]][j])--r;
			q[++r]=i,f[0][1][j]=min(f[0][1][j],s[0][i][j]);
		}
		for(int i=k+1; i<=n; ++i) {
			while(l<=r&&i-q[l]+1>k)++l;
			if(l<=r) f[0][i-k+1][j]=s[0][q[l]][j];
			f[0][i-k+1][j]=min(f[0][i-k+1][j],s[0][i][j]);
			while(l<=r&&s[0][i][j]<=s[0][q[r]][j])--r;
			q[++r]=i;
		}
	}
	
	for(int j=1,l=1,r=0; j<=m; ++j) {
		for(int i=1; i<=k; ++i) {
			while(l<=r&&s[1][i][j]>=s[1][q[r]][j])--r;
			q[++r]=i,f[1][1][j]=max(f[1][1][j],s[1][i][j]);
		}
		for(int i=k+1; i<=n; ++i) {
			while(l<=r&&i-q[l]+1>k)++l;
			if(l<=r) f[1][i-k+1][j]=s[1][q[l]][j];
			f[1][i-k+1][j]=max(f[1][i-k+1][j],s[1][i][j]);
			while(l<=r&&s[1][i][j]>=s[1][q[r]][j])--r;
			q[++r]=i;
		}
	}
	
	int ans=0xccfccfccfccfccf;
	for(int i=1;i+k-1<=n;++i) for(int j=1;j+k-1<=m;++j) ans=min(ans,f[1][i][j]-f[0][i][j]);
	cout<<ans;
	return 0;
}