P2216 [HAOI2007]理想的正方形 (單調隊列)

題目連結：P2216 [HAOI2007]理想的正方形

題目描述

有一個 \(a\times b\)的整數組成的矩陣，現請你從中找出一個 \(n\times n\)的正方形區域，使得該區域所有數中的最大值和最小值的差最小。

輸入格式

第一行為3個整數，分别表示a,b,n的值

第二行至第a+1行每行為b個非負整數，表示矩陣中相應位置上的數。每行相鄰兩數之間用一空格分隔。

輸出格式

僅一個整數，為 \(a\times b\)矩陣中所有“ \(n\times n\)正方形區域中的最大整數和最小整數的內插補點”的最小值。

輸入輸出樣例

輸入 #1

5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
           

輸出 #1

1
           

說明/提示

問題規模

（1）矩陣中的所有數都不超過1,000,000,000

（2）20%的資料2<=a,b<=100,n<=a,n<=b,n<=10

（3）100%的資料2<=a,b<=1000,n<=a,n<=b,n<=100

思路

單調隊列

二維 RMQ 問題。

設原矩陣為 m[][]，用單調隊列求每行的最大/最小值，分别存入兩個矩陣 maxr[][] 和 minr[][]。maxr[i][j] 代表 m[i][j] 到 m[i][j + n - 1] 的最大值，minr[i][j] 代表 m[i][j] 到 m[i][j + n - 1] 的最小值。

接下來對這兩個矩陣用單調隊列求每列的最大/最小值，分别存入兩個矩陣 maxc[][] 和 minc[][]。maxr[i][j] 代表 m[i][j] 到 m[i + n - 1][j + n - 1] 的最大值，minr[i][j] 代表 m[i][j] 到 m[i + n - 1][j + n - 1] 的最小值。

最後周遊 maxc[][] 和 minc[][] 即可。

代碼

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;

int m[maxn][maxn];

int maxr[maxn][maxn], maxc[maxn][maxn];
int minr[maxn][maxn], minc[maxn][maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b, n;
    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 l = 1, r = 1;
        int L = 1, R = 1;
        int q1[maxn] = {0, l}, q2[maxn] = {0, L};
        for(int j = 2; j <= b; ++j) {
            while(r >= l && j - q1[l] >= n) ++l;
            while(r >= l && m[i][j] <= m[i][q1[r]]) --r;
            q1[++r] = j;
            if(j >= n) minr[i][j - n + 1] = m[i][q1[l]];

            while(R >= L && j - q2[L] >= n) ++L;
            while(R >= L && m[i][j] >= m[i][q2[R]]) --R;
            q2[++R] = j;
            if(j >= n) maxr[i][j - n + 1] = m[i][q2[L]];
        }
    }

    for(int i = 1; i <= b - n + 1; ++i) {
        int l = 1, r = 1;
        int L = 1, R = 1;
        int q1[maxn] = {0, l}, q2[maxn] = {0, L};
        for(int j = 2; j <= a; ++j) {
            while(r >= l && j - q1[l] >= n) ++l;
            while(r >= l && minr[j][i] <= minr[q1[r]][i]) --r;
            q1[++r] = j;
            if(j >= n) minc[j - n + 1][i] = minr[q1[l]][i];

            while(R >= L && j - q2[L] >= n) ++L;
            while(R >= L && maxr[j][i] >= maxr[q2[R]][i]) --R;
            q2[++R] = j;
            if(j >= n) maxc[j - n + 1][i] = maxr[q2[L]][i];
        }
    }
    int ans = inf;
    for(int i = 1; i <= a - n + 1; ++i) {
        for(int j = 1; j <= b - n + 1; ++j) {
            ans = min(ans, maxc[i][j] - minc[i][j]);
        }
    }
    cout << ans << endl;
    return 0;
}