CodeChef Chef and Rectangle Array

まためっちゃ久しぶりに記事書いてますね…最近心に余裕がなくて全然解いてない…

問題

Contest Page | CodeChef

N*M の行列が与えられる。これに対して Q 個のクエリが投げられるのでそれぞれに答えよ。

• 整数 a, b が与えられるので, N*M 行列の中にある a*b の部分行列を考えて(部分行列の最大値)*a*b - (部分行列の各要素の和) を最小化せよ。

解法

要するに a*b 行列の最大値と和を高速で求められれば良さそうです。各要素の和は長方形でよく使うアレで求められます。

最大値については, sliding window テクニックを使いました。
mayokoex.hatenablog.com

まず各行について, memo[row][col] = (row 行目で, col 列目からの b 個の要素における最大値) を求めます。

で, 今度は各行について sliding window テクニックを使うと a*b 行列の中での最大値が求められるわけです。

const int MAXN = 1010;
int A[MAXN][MAXN];
int sum[MAXN][MAXN];

// [y0, y1), [x0, x1)
int getSum(int y0, int x0, int y1, int x1) {
    return sum[y1][x1] - sum[y1][x0] - sum[y0][x1] + sum[y0][x0];
}

int memo[MAXN][MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++)
        cin >> A[i][j];
    for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) {
        sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + A[i-1][j-1];
    }
    int Q;
    cin >> Q;
    while (Q--) {
        int a, b;
        cin >> a >> b;
        for (int row = 0; row < N; row++) {
            deque<pii> window;
            for (int col = 0; col < M; col++) {
                while (!window.empty() && window.back().first <= A[row][col])
                    window.pop_back();
                window.emplace_back(A[row][col], col);
                while (window.front().second <= col-b)
                    window.pop_front();
                if (col >= b-1) {
                    memo[row][col-b+1] = window.front().first;
                }
            }
        }
        int ans = 1e9;
        for (int col = 0; col+b <= M; col++) {
            deque<pii> window;
            for (int row = 0; row < N; row++) {
                while (!window.empty() && window.back().first <= memo[row][col]) 
                    window.pop_back();
                window.emplace_back(memo[row][col], row);
                while (window.front().second <= row-a)
                    window.pop_front();
                if (row >= a-1) {
                    ans = min(ans, a*b*window.front().first - getSum(row-a+1, col, row+1, col+b));
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}