自动搬运

查看原文

来自洛谷，原作者为

	Ahws_rwhy 真実はいつもひとつ！ AH 目前在役Oier& 每日一%@dws_t7760

搬运于2025-08-24 23:01:33，当前版本为作者最后更新于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;
	}
}