P14528 [BYOI R1] 雨后屋檐 题解

Getaway_Car · 2025-07-26 17:29:16 · 题解

:::info[题面 & 提示]

P1318 加强版，区别在于本题包含多个询问，每个询问给定查询的区间 [l, r] 与最大水面高度 H，强制在线。P1318 的做法对本题有一些启发。

:::

设 n, q 同阶。

考虑本题的难点在哪里。发现屋顶的两侧不一定足够高，所以一些水会流出去。

考虑特殊性质，此时没有水会流出去。考虑这时该怎么做。发现此时的答案为：

即：

发现这个问题相当于二维数点，于是考虑使用可持久化权值线段树解决，详见 P10814。

去掉特殊性质，容易发现，只要一个区间两侧的屋顶高度 \ge H，就可以用上述方法解决。于是我们尝试从询问的区间 [l, r] 中找到一个两端高度都不小于 H 的子区间。

令 H \leftarrow \min(\max_{i = l}^r \{h_i\}, H)，这对答案没有影响；令 L 表示区间左侧第一个满足 h_i \ge H 的位置 i；同理，令 R 表示区间右侧第一个满足 h_i \ge H 的位置 i。计算 L, R 可以通过线段树二分解决。显然 L, R 一定存在。

此时问题被划分为了 [l, L)、[L, R] 与 (R, r] 三段。第二段是前文中已经讨论的情况，是容易算出水的体积的。一三段的问题是对称的，所以接下来讨论第一段。

接下来是 P1318 的结论。

设位置 i 的水面相对地面高度为 a_i。特别地，若位置 i 没有水，则令 a_i = h_i。容易注意到，\forall i \in [l, L)，有：

注意到前者一定小于后者，于是我们就有了第一段的答案：

后者是容易维护的，考虑如何维护前者。前者是区间前缀最大值之和，即 P5648。直接使用 P5648 的做法即可。

直接把三段的答案加在一起就可以得到总答案。

时间复杂度 O(n \log n)，空间复杂度 O(n \log n)，有巨大常数。

:::info[一个常数优化]{open}

考虑优化计算 L 的过程。

按照 P5648 的做法，我们利用单调栈建了一棵树。注意到在向右连边的树中，L 一定是 l 的父亲或其本身，所以可以通过树上倍增来计算 L。