Painting the Barn (USACO Gold 2019 US February)

新画的矩形是不重合的，所以原来需要至少有 $K-1$ 重油漆的地方才有可能。
因此和我们相关的只有 $k-1$ 和 $k$ 重的位置，把这些位置设成 $1$ 和 $-1$ ，其它位置设成 $0$ 。这样就变成2D矩形求和问题。例如一个可能的地图是这样的：

    0  0  0  0  0  0  0  0
    0  0  1  1  1  1  1  1
    0  0  1 -1 -1 -1 -1  1
    0  0  1 -1 -1 -1 -1  1
    0  1 -1  0 -1 -1 -1  1
    0  1 -1 -1  1  1  1  1
    0  1  1  1  0  0  0  0
    0  0  0  0  0  0  0  0

先考虑只绘制一个矩形的相对简单的情况，这时就是求上面的地图里最大和的矩形，这是个标准问题，可以通过把Kadane算法扩展到2维来实现，复杂度是 $\mathcal{O}(n^3)$ 。
现在考虑完整问题，我们要画两个矩阵，怎样降低求两个不相交的矩形和的搜索复杂度？注意到两个矩形一定在横向或者纵向上是分开的，所以可以把坐标分成两段，枚举所有分隔方法来做。我们把上一步找一个最大和矩形过程中的数据存下来之后，枚举分隔找两个矩形的最大和，就可以在 $\mathcal{O}(N)$ 解决，所以最后完整的复杂度还是 $\mathcal{O}(n^3)$ 。当然分隔有两种，横向和纵向。

实现细节比较多，代码量较大。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n,K;
int d[205][205];    // delta when scanning along y
int a[205][205];    // # of paints per cell
int ps[205][205];   // row prefix sums
int ps2[205][205];  // col prefix sums
vector<int> rsum[205][205];     // rsum[x1][x2][y], per-row subarray sum
vector<int> csum[205][205];     // csum[y1][y2][x], per-col subarray sum
 
int top[205], bottom[205];   // best results at or above/below i-th row
int left[205], right[205];   // best results at or to the left/right of i-th column
 
int main() {
    scanf("%d %d", &n, &K);
    for (int i = 0; i < n; i++) {
        int x1,y1,x2,y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        for (int y = y1; y < y2; y++)
            d[y][x1]++, d[y][x2]--;
    }
    for (int y = 0; y < 200; y++)
        for (int x = 0; x < 200; x++)
            a[y][x] = x == 0 ? d[y][x] : a[y][x-1] + d[y][x];   // calc paints per cell
    int total = 0;
    for (int y = 0; y < 200; y++)
        for (int x = 0; x < 200; x++) {
            a[y][x] = a[y][x] == K-1 ? 1 : 
                      a[y][x] == K ? -1 : 0;                    // K-1 => 1, K => -1
            total += a[y][x] == -1 ? 1 : 0;
        }
    for (int y = 0; y <= 200; y++)
        for (int x = 0; x <= 200; x++)
            ps[y][x+1] = a[y][x] + ps[y][x];    // calc per row prefix sum
    for (int x1 = 0; x1 <= 200; x1++)
        for (int x2 = x1; x2 <= 200; x2++) {
            int cur = 0;
            for (int y = 0; y <= 200; y++) {
                cur = max(cur + ps[y][x2]-ps[y][x1], 0);
                bottom[y+1] = max(bottom[y], bottom[y+1]);
                bottom[y+1] = max(bottom[y+1], cur);   // calc bottom[i]
            }
            cur = 0;
            for (int y = 200; y >= 0; y--) {
                cur = max(cur + ps[y][x2]-ps[y][x1], 0);
                top[y] = max(top[y], top[y+1]);
                top[y] = max(top[y], cur);   // calc top[i]
            }
        }
    for (int x = 0; x <= 200; x++)
        for (int y = 0; y <= 200; y++)
            ps2[y+1][x] = a[y][x] + ps2[y][x];  // per col prefix sum
    for (int y1 = 0; y1 <= 200; y1++)
        for (int y2 = y1; y2 <= 200; y2++) {    // 1d kadane algorithm: max subarray sum
            int cur = 0;
            for (int x = 0; x <= 200; x++) {
                cur = max(cur + ps2[y2][x]-ps2[y1][x], 0);
                left[x+1] = max(left[x], left[x+1]);
                left[x+1] = max(left[x+1], cur);   // calc left[i]
            }
            cur = 0;
            for (int x = 200; x >= 0; x--) {
                cur = max(cur + ps2[y2][x]-ps2[y1][x], 0);
                right[x] = max(right[x], right[x+1]);
                right[x] = max(right[x], cur);   // calc right[i]
            }
        }
    int ans = -1e9;
    for (int x = 0; x <= 200; x++) 
        ans = max(ans, left[x] + right[x]);
    for (int y = 0; y <= 200; y++)
        ans = max(ans, top[y] + bottom[y]);
    printf("%d", total + ans);
    return 0;
}