题解：P12019 [NOISG 2025 Finals] 洪水

· · 题解

绝世好题！！！

速报：本题复杂度已达到输入同级 \mathcal O(hw)！！！

注意到每个结点能淹没的点一定是一个矩形，不然可以继续扩张。

我们在矩形外面围一层 1。

考虑一个作为答案的矩形长什么样，容易发现该矩形的边界一定全是 1，且不能存在一行（列） 1 将其分开。

一个位置的答案矩形即为最小的包含它的这种矩形的大小。

记第 i 个这种矩形的大小为 x_i \times y_i，我们断言 \sum{(x_i+y_i)} \le hw。

考虑证明这个理论：

首先这样的矩形只能包含或相离，否则会有两个矩形互相把对方切开。

我们对矩形的包含关系建一棵树。

考虑每个矩形和它父亲矩形的重叠部分，我们证明其不可能包含一组对边。

若其包含一组对边，则该矩形会把父亲矩形划分成两个部分，不满足合法矩形要求。

那么它至少有一对长和宽是不与父亲重合的，即 \sum (x_i+y_i) \le hw。

接下来我们需要求出这些极大矩形。

考虑枚举左边界 x。记 x 上的建筑物为 0,i_1,i_2,\cdots,i_k,m+1，f_p 为 i_p 向左延伸的最远距离。

那么一个合法的上下边界 i_p,i_q 一定满足 \min(f_p,f_q) > \max\limits_{i=p+1}^{q-1} f_i，这个可以单调栈求出。

对于一对合法的 i_p,i_q，我们可以暴力从 x 出发找右边界，容易证明这个的复杂度是均摊 \mathcal O(hw) 的。

接下来就是做矩形 checkmin，求全局值。这部分由于周长是 \mathcal O(hw) 级别的可以对每行开一个 \mathcal O(w) 并查集，将矩形从小到大排序后对每行做区间覆盖。排序使用计数排序即可做到时间复杂度 \mathcal O(hw)。

qoj 最优解。