$\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;
}