题目链接：Luogu 2219

为了增添公园的景致，现在需要在公园中修筑一个花坛，同时在画坛四周修建一片绿化带，让花坛被绿化带围起来。

如果把公园看成一个 $M\times N$ 的矩形，那么花坛可以看成一个 $C\times D$的矩形，绿化带和花坛一起可以看成一个 $A\times B$ 的矩形。

如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度 $X_{i,j}$ 之和，那么，绿化带的肥沃度 = $A\times B$ 块的肥沃度 - $C\times D$ 块的肥沃度。

为了使得绿化带的生长得旺盛，我们希望绿化带的肥沃度最大。

数据范围：$1\le M,N\le 1000$，$1\le A\le M$，$1\le B\le N$，$1\le C\le A - 2$，$1\le D\le B - 2$，$1\le X_{i,j}\le 100$。

Solution

首先发现，在 $A\times B$ 矩形确定时，$C\times D$ 矩形可行的右下角形成了一个 $(A-C-1)\times (B -D - 1)$ 的矩形。由于这是一个二维问题，我们首先考虑一个一维问题：对于所有的 $i,j$ 求出右下角在 $(i,j - (B - D - 1) + 1)$ 到 $(i,j)$ 范围的 $C\times D$ 矩形的最小值。

很显然行是独立的，我们对于每一行可以用单调队列处理，设这个值为 $g(i,j)​$。

之前是将点变成线，接下来考虑将得到的线变成面。我们枚举列 $j$，然后对于所有的 $i$ 求出 $\min_{i - (A - C - 1) + 1\le k \le i}g(k,j)$。这个过程显然也可以使用单调队列实现。记这个值为 $f(i,j)$。

通过分析，我们可以发现当 $A\times B$ 矩形的右下角为 $(i + 1, j + 1)$ 时，可行的 $C\times D$ 矩形右下角为矩形 $(i - (A - C - 1) + 1, j - (B - D - 1) + 1), (i, j)$。这个值即为 $f(i,j)$。直接统计答案即可。

时间复杂度：$\mathcal O(NM)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 1e3 + 5;

int n, m, A, B, C, D, a[N][N], sum[N][N], k[N][N], g[N][N], f[N][N], q[N];

int query(int x1, int y1, int x2, int y2) {
    return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
}
void init(int x, int y, int h[N][N]) {
    for (int i = x; i <= n; i++) {
        for (int j = y; j <= m; j++) {
            h[i][j] = query(i - x + 1, j - y + 1, i, j);
        }
    }
}
int main() {
    scanf("%d%d%d%d%d%d", &n, &m, &A, &B, &C, &D);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
        }
    }
    init(C, D, k);
    for (int i = 1; i <= n; i++) {
        int l = 1, r = 0;
        for (int j = 1; j <= m; j++) {
            while (l <= r && q[l] < j - (B - D - 1) + 1) l++;
            while (l <= r && k[i][q[r]] >= k[i][j]) r--;
            q[++r] = j;
            g[i][j] = k[i][q[l]];
        }
    }
    for (int j = 1; j <= m; j++) {
        int l = 1, r = 0;
        for (int i = 1; i <= n; i++) {
            while (l <= r && q[l] < i - (A - C - 1) + 1) l++;
            while (l <= r && g[q[r]][j] >= g[i][j]) r--;
            q[++r] = i;
            f[i][j] = g[q[l]][j];
        }
    }
    int ans = 0;
    for (int i = A; i <= n; i++) {
        for (int j = B; j <= m; j++) {
            ans = std::max(ans, query(i - A + 1, j - B + 1, i, j) - f[i - 1][j - 1]);
        }
    }
    printf("%d\n", ans);
    return 0;
}