oier_2134568 20:35:30
#include<bitsdc++.h>
using namespace std;
int n,m,k;
const int N = 1005;
int a[N][N],xn[N][N],xx[N][N];
int _yn[N][N],yx[N][N];
int qn[N],qnhd,qntl;
int qx[N],qxhd,qxtl;
int main(){
    cin >> n >> m >> k;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            cin >> a[i][j];
    for(int i = 1;i <= n;i ++){
        qn[1] = qx[1] = qnhd = qntl = qxhd = qxtl = 1;
        for(int j = 2;j <= m;j ++){
            while(qnhd <= qntl && a[i][qn[qntl]] >= a[i][j]) qntl --;
            while(qxhd <= qxtl && a[i][qx[qxtl]] <= a[i][j]) qxtl --;
            qn[++qntl] = j,qx[++qxtl] = j;
            while(qnhd <= qntl && j - qn[qntl] >= k) qnhd ++;
            while(qxhd <= qxtl && j - qx[qxtl] >= k) qxhd ++;
            if(j >= k) xn[i][j-k+1] = a[i][qn[qnhd]],xx[i][j-k+1] = a[i][qx[qxhd]];
        }
    }
    for(int i = 1;i <= m-k+1;i ++){
        qn[1] = qx[1] = qnhd = qntl = qxhd = qxtl = 1;
        for(int j = 2;j <= n;j ++){
            while(qnhd <= qntl && xn[qn[qnhd]][i] >= xn[j][i]) qntl --;
            while(qxhd <= qxtl && xx[qx[qxhd]][i] <= xx[j][i]) qxtl --;
            qn[++qntl] = j,qx[++qxtl] = j;
            while(qnhd <= qntl && j - qn[qnhd] + 1 > k) qnhd ++;
            while(qxhd <= qxtl && j - qx[qxhd] + 1 > k) qxhd ++;
            if(j >= k) _yn[j-k+1][i] = xn[qn[qnhd]][i],yx[j-k+1][i] = xx[qx[qxhd]][i];
        }
    }
    int ans = 2e9;
    for(int i = 1;i <= n-k+1;i ++)
        for(int j = 1;j <= m-k+1;j ++)
            ans = min(ans,yx[i][j]-_yn[i][j]);
    cout << ans;
}

qn->qmin最小值单调队列

qx->qmax最大值单调队列

xn,xx,yn,yx命名规则同上