第四次,希望有人能回,该对必关

#include <bits/stdc++.h>
#define ll long long
#define mx 1005
using namespace std;

ll n,m,k,fx,fn,bx,bn,ans;
ll a[mx][mx],dqx[mx],dqn[mx]; 
ll hx[mx][mx],hn[mx][mx];
ll lx[mx][mx],ln[mx][mx];

int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%lld",&a[i][j]);
	for(int i=1;i<=n;i++){
		fx=fn=bx=bn=dqx[1]=dqn[1]=1;
		for(int j=2;j<=m;j++){
			while(fx<=bx&&a[i][dqx[bx]]<=a[i][j]) bx--;
			while(fn<=bn&&a[i][dqn[bn]]>=a[i][j]) bn--;
			dqx[++bx]=j;
			dqn[++bn]=j;
			while(dqx[fx]<=j-k) fx++;
			while(dqn[fn]<=j-k) fn++;
			if(j>=k) hx[i][j-k+1]=a[i][dqx[fx]],hn[i][j-k+1]=a[i][dqn[fn]];
		}
	}
	for(int i=1;i<=m-k+1;i++){
		fx=fn=bx=bn=dqx[1]=dqn[1]=1;
		for(int j=2;j<=n;j++){
			while(fx<=bx&&hx[dqx[bx]][i]<=a[j][i]) bx--;
			while(fn<=bn&&hn[dqn[bn]][i]>=a[j][i]) bn--;
			dqx[++bx]=j;
			dqn[++bn]=j;
			while(dqx[fx]<=j-k) fx++;
			while(dqn[fn]<=j-k) fn++;
			if(j>=k) lx[j-k+1][i]=hx[dqx[fx]][i],ln[j-k+1][i]=hn[dqn[fn]][i];
		}
	}
	ans=0x3f3f3f3f;
	for(int i=1;i<=n-k+1;i++)
		for(int j=1;j<=m-k+1;j++)
			ans=min(ans,lx[i][j]-ln[i][j]);
	cout<<ans+1<<endl;
	return 0;
}