题解：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 最优解。