单调队列维护区间最大值最小值。。。

用 X[ i ][ j ] 表示 第 i 行 从第 j 列到第 j+n-1 列 的最大值。。。

反之，用 x[ i ][ j ] 表示最小值。。。

接下来用同种方法。。。利用 X 和 x 对每一列进行维护。。。记作 Y[ i ][ j ] y[ i ][ j ]

最后。。。枚举 i j 取最小的 Y[ i ][ j ] - y[ i ][ j ] 就是答案。。。

呆码：

#include
      
       #include
       
        using namespace std;int a,b,n,head1,head2,tail1,tail2,ans=999999999;int c[1010][1010],q1[1010],q2[1010];int X[1010][1010],x[1010][1010],Y[1010][1010],y[1010][1010];int main(){    scanf("%d%d%d",&a,&b,&n);    for(int i=1;i<=a;i++)        for(int j=1;j<=b;j++)            scanf("%d",&c[i][j]);    for(int i=1;i<=a;i++)    {        head1=head2=tail1=tail2=q1[1]=q2[1]=1;        for(int j=2;j<=b;j++)        {            while(head1<=tail1 && c[i][j]>=c[i][q1[tail1]]) tail1--;            while(head2<=tail2 && c[i][j]<=c[i][q2[tail2]]) tail2--;            q1[++tail1]=j; q2[++tail2]=j;            while(j-q1[head1]>=n) head1++;            while(j-q2[head2]>=n) head2++;            if(j>=n) X[i][j-n+1]=c[i][q1[head1]];            if(j>=n) x[i][j-n+1]=c[i][q2[head2]];        }    }    for(int i=1;i<=b-n+1;i++)    {        head1=head2=tail1=tail2=q1[1]=q2[1]=1;        for(int j=2;j<=a;j++)        {            while(head1<=tail1 && X[j][i]>=X[q1[tail1]][i]) tail1--;            while(head2<=tail2 && x[j][i]<=x[q2[tail2]][i]) tail2--;            q1[++tail1]=j; q2[++tail2]=j;            while(j-q1[head1]>=n) head1++;            while(j-q2[head2]>=n) head2++;            if(j>=n) Y[j-n+1][i]=X[q1[head1]][i];            if(j>=n) y[j-n+1][i]=x[q2[head2]][i];        }    }    for(int i=1;i<=a-n+1;i++)        for(int j=1;j<=b-n+1;j++)            ans=min(ans,Y[i][j]-y[i][j]);    printf("%d\n",ans);}