题解：P10817 [EC Final 2020] Rectangle Flip 2

Ahws_rwhy · 2024-07-29 15:57:41 · 题解

感谢我的队友，给了我一定的思路！

队友看了题，说：“用单调栈，\mathcal O(N ^ 3)，能过！”我看看了题，发现这做法可行。但是我想到了一种思路（本质一样，没用单调栈），于是，便写了下去 \dots 大约 50\min 切了。

题解：

很简单，对于每个删除的点，看会影响多少新矩形。枚举矩阵的左右每个位置，维护其的上下界 （ 可以外枚举下边界，确定下边界后，内枚举上边界 ），影响的数量是 (x - l + 1 ) \times (r - x + 1)（l,r 代表此时上下边界形成公共部分的左边 l 与右边 r），固定 x，枚举 y，就行了。

求完这个点会影响的好的矩形的数量，就在看这个点会对后面的点产生的影响。

这个影响无非就是，对后面的点在求每行能扩的最大边界的产生影响。

时间复杂度 \mathcal O(N ^ 3)。

code:

void solve(int x, int y) {
    int bb = b[x][y], cc = c[x][y];
    for (int i = y; i >= 1; i--) {
        if (a[x][i] == 1) break;
        int bbb = b[x][y], ccc = c[x][y];
        bb = max(b[x][i], bb), cc = min(c[x][i], cc);
        for (int j = y; j <= m; j++) {
            if (a[x][j] != 0) break;
            bbb = max(b[x][j], bbb), ccc = min(c[x][j], ccc);
            maxx =  max(bb, bbb), minn = min(cc, ccc);
            ans -= (x - maxx + 1 ) * (minn - x + 1);
        }
    }
    a[x][y] = 1;
    for (int i = x - 1; i >= 1; i--) {
        if (a[i][y] == 0 )c[i][y] = x - 1;
        else break;
    }
    for (int i = x + 1; i <= n; i++) {
        if (a[i][y] == 0) b[i][y] = x + 1;
        else break;
    }
}