题解：P11699 [ROIR 2025] 酸雨

cwxcplh · 2026-07-20 16:20:43 · 题解

简单题，应该是因为超级难调的 DS 才提到紫的（然后它告诉我这是模拟考试 T1）。

首先我们需要想办法快速求出第 x 块的开头，显然我们可以用一棵线段树维护每个位置目前属于哪个块，然后再在线段树上二分求出开头。

找到了这个块的开头，考虑如何维护两个块的答案。首先我们肯定要记录一个 ans 表示当前的答案，然后我们要将两个块合并起来，这个怎么更新 ans？

我们考虑两边块中的最大高度，找到最大高度更小的那一块，显然那一块可以直接被平推了。假设高度更小的是后面那一块，那么我们找出左边那一块最近的比最大高度要高的位置：

现在这个序列被我们划分成了四部分，我们对四部分分别考虑。最左边那一部分因为右边有蓝色柱子帮忙挡着，所以不用更新；第二部分显然水位线应该更新到红色柱子的高度，所以总贡献是 cnt\times h-sum（cnt 表示个数，h 是红柱子高度，sum 是区间和）。

第三部分显然左边水位线的最大高度已经超过了右边，所以我们相当于直接对右边考虑即可；第四部分跟第三部分同理。

所以我们还需要维护两个东西：lans,rans。分别表示仅考虑左边（或右边）时的答案。那么上面的最后一种更新其实就是 ans=rans。

最终答案显然就是这一段的 ans。

再看看图：

当然，你可以在更新完绿色段的 rans 后再把绿色段和橙色段看成同一种也行。

现在说说 lans 和 rans，这玩意儿显然也是好维护的，比如上面那张图中，绿色部分的 rans 显然要更新，橙色部分的 lans 则需要更新，而紫色段显然因为有蓝色柱子所以不用更新。

左边比右边小也是显然的。

上述操作理论上来讲都可以在 O(\log n) 的复杂度内实现，但因为比较复杂，所以我在一个地方稍微用了一下 O(\log^2 n) 的做法。

时间复杂度：O(n\log^2n)（也可以 O(n\log n)）。

代码：太长了我放这了。