题目链接：###
题目分析：###
这道题对于我这种菜鸡来说其实有点难……值得一做
核心思想：分别在行和列上维护单调队列
用x_min[i][j]表示以mapp[i][j]为起点向右推n个里的最小值，最大值同理
用y_min[i][j]表示以mapp[i][j]为起点向下推n个里的最小值，最大值同理
先用mapp更新x_min，x_max，再用x_min，x_max分别更新y_min，y_max
时间复杂度似乎O((a^2)*n)，能过
参考了洛谷第一篇题解，挺优秀的
代码：###
#include<bits/stdc++.h>
#define maxa (1000+5)
#define maxn (100+5)
using namespace std;
inline int read(){
int cnt=0,f=1;char c;
c=getchar();
while(!isdigit(c)){
if(c=='-')f=-f;
c=getchar();
}
while(isdigit(c)){
cnt=cnt*10+c-'0';
c=getchar();
}
return cnt*f;
}
int a,b,n;
int mapp[maxa][maxa];
int x_max[maxa][maxa],x_min[maxa][maxa];
int y_max[maxa][maxa],y_min[maxa][maxa];
int q1[maxa],q2[maxa];//q1->max,q2->min
int l1,r1,l2,r2;
int main(){
a=read();b=read();n=read();
for(register int i=1;i<=a;i++)
for(register int j=1;j<=b;j++)mapp[i][j]=read();
for(register int i=1;i<=a;i++){
l1=l2=r1=r2=1;
q1[1]=q2[1]=1;
for(register int j=2;j<=b;j++){
while(mapp[i][j]>=mapp[i][q1[r1]]&&l1<=r1)r1--;
while(mapp[i][j]<=mapp[i][q2[r2]]&&l2<=r2)r2--;
q1[++r1]=j;q2[++r2]=j;
while(j-q1[l1]>=n&&l1<=r1)l1++;
while(j-q2[l2]>=n&&l2<=r2)l2++;
if(j>=n)x_max[i][j-n+1]=mapp[i][q1[l1]],x_min[i][j-n+1]=mapp[i][q2[l2]];
}
}
for(register int i=1;i<=b-n+1;i++){
l1=l2=r1=r2=1;
q1[1]=q2[1]=1;
for(register int j=2;j<=a;j++){
while(x_max[j][i]>=x_max[q1[r1]][i]&&l1<=r1)r1--;
while(x_min[j][i]<=x_min[q2[r2]][i]&&l2<=r2)r2--;
q1[++r1]=j;q2[++r2]=j;
while(j-q1[l1]>=n&&l1<=r1)l1++;
while(j-q2[l2]>=n&&l2<=r2)l2++;
if(j>=n)y_max[j-n+1][i]=x_max[q1[l1]][i],y_min[j-n+1][i]=x_min[q2[l2]][i];
}
}
int ans=1<<30;
for(register int i=1;i<=a-n+1;i++)
for(register int j=1;j<=b-n+1;j++)
if(y_max[i][j]-y_min[i][j]<ans)ans=y_max[i][j]-y_min[i][j];
printf("%d
",ans);
return 0;
}