传送门

思路

双重单调队列，单调队列练手好题。

代码

#include
#define MAXN 1010
using namespace std;
int M[MAXN][MAXN], rowmax[MAXN][MAXN], rowmin[MAXN][MAXN],
colmax[MAXN][MAXN], colmin[MAXN][MAXN], q[MAXN];
int main(void)
{
    int a = 0, b = 0, n = 0;
    cin >> a >> b >> n;
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
            cin >> M[i][j];
    for (int i = 1; i <= a; i++)
    {
        int head = 0, tail = 0;
        for (int j = 1; j <= b; j++)
        {
            while (head < tail && q[head] + n <= j)
                head++;
            while (head < tail && M[i][q[tail - 1]] < M[i][j])
                tail--;
            q[tail] = j; tail++;
            if (j >= n) rowmax[i][j - n + 1] = M[i][q[head]];
        }
        head = 0, tail = 0;
        for (int j = 1; j <= b; j++)
        {
            while (head < tail && q[head] + n <= j)
                head++;
            while (headM[i][j])
                tail--;
            q[tail] = j; tail++;
            if (j >= n) rowmin[i][j - n + 1] = M[i][q[head]];
        }
    }
    for (int j = 1; j <= b - n + 1; j++)
    {
        int head = 0, tail = 0;
        for (int i = 1; i <= a; i++)
        {
            while (head < tail && q[head] + n <= i)
                head++;
            while (head < tail && rowmax[q[tail - 1]][j] < rowmax[i][j])
                tail--;
            q[tail] = i; tail++;
            if (i >= n) colmax[i - n + 1][j] = rowmax[q[head]][j];
        }
        head = 0, tail = 0;
        for (int i = 1; i <= a; i++)
        {
            while (head < tail && q[head] + n <= i)
                head++;
            while (headrowmin[i][j])
                tail--;
            q[tail] = i; tail++;
            if (i >= n) colmin[i - n + 1][j] = rowmin[q[head]][j];
        }
    }
    long long ans = INT32_MAX;
    for (int i = 1; i <= a - n + 1; i++)
        for (int j = 1; j <= b - n + 1; j++)
            ans = min(ans, (long long)(colmax[i][j] - colmin[i][j]));
    cout << ans;
    return 0;
}