POI2018 水箱 题解
$\text{Description}$
已知有一个 $n\times m\times H$ 的长方体，对于水平面上的相邻两格间，会有一堵厚度忽略不计的墙，从最低一层开始，到第 $h_{i,j}\ge 1$ 层。
定义一种装水方式是合法的，当且仅当：
- 某一个格子装了水，则它是最低一层的格子或者其竖直向下的格子装了水。
- 某一个格子装了水，则它在水平面上的相邻四个格子要么是水，要么中间有堵墙。
求有多少种合法的装水方式，对 $10^9+7$ 取模。
$n\times m\le 5\times 10^5,H\le 10^9$
$\text{Solution}$
考虑某一个位置有墙，则它的正下方必然有墙（或者是最底一层），那么从下向上计算的过程实际上可以看成不断去掉一堵墙，其实就是让两个格子连通的操作，由于墙的高度至少为 $1$，故一开始所有格子都不连通。对于某一层 $h$，我们发现高度大于等于 $h$ 的墙会将该平面分成若干个连通块，对于某个连通块，若某一个装的水高度大于等于 $h$，则该连通块内的所有格子装的水都相等。
换言之，我们设某个连通块装水的方案数为 $f_i$，该连通块内的最高的墙高度 $h_i$，则某次去掉一堵高度为 $h$ 的墙时，不妨设它让 $x,y$ 两个连通块连通了（若两者已连通则无需考虑），那么新连通块 $t$ 的方案数正是 $f_t=f_xf_y+f_x(h-h_y)+f_y(h-h_x)+(h-h_x)(h-h_y)=(f_x+h-h_x)\times(f_y+h-h_y)$，即两者装的水高度都不超过各自内部最高的墙，某一个超过了，两者都超过了的方案数之和。
注意到我们只需让两个连通块连通，故采用并查集，并在代表元处维护 $f$ 即可。
最后需将所有连通块的答案加上 $H-h_x$ 后再相乘，具体实现细节见代码。
时间复杂度 $\mathcal O(nm\log(nm))$。
$\text{Code}$
1 |
|