题解：CF2234F Vessels, Heights and Two Versions (Hard Version)

_Tooler_Fu_ · 2026-06-11 11:49:33 · 题解

赛时有室友在打 CS 然后被 C 卡了一小时最后没时间检查F的环形数组没开两倍惨遭TLE赛后1min过……

这题沿用 C 题的思路。

首先对于当前的柱子 i，若下一个柱子 i+1 的高度大于当前的 i，即 a_{i+1} > a_i，那么这中间的水面高度就都不能超过 a_i。

如果下一个柱子 i+1 高度小于当前的 i，即 a_{i+1} < a_i，我们观察样例 2，不难发现我们会找到一个大于 i 的最小的 j，使得 a_i \le a_j，然后这其中的水面都可以被 a_i , a_j 所拦截，由于 a_i \le a_j，我们取 a_i 的高度乘以 j-i+1 即可。

然而这样做会有问题，如果到最后一根柱子但最后的柱子并不是最高的，用上述的方法做一定得不到答案，这种情况怎么办？

其实好做，我们可以直接标记最高的柱子的位置 max，假设当前的区间是 [i,i+n-1]，对 [i,max]正着做 和 [max,i+n-1] 倒着做即可。

怎么统计答案：由于最高的柱子一定在区间之内，而且其左右的水面情况相互独立，因而我们可以使用两个数组 ansl 与 ansr 来统计 每个数到 max 的最大水面容量，最后对于每个 i，ansl_i+ansr_i+n-1 就是最后的答案。

关于 ansl 与 ansr 的计算，这里拿 ansl 举例，依旧找到下一个比当前柱子 i 大的柱子 j，然后继承 ansl_j 的数值（这里要倒着找，同理 ansr 要正着找），加上 (r-i+1) \times a_i 就行了。

找 j 可以使用单调栈 O(n) 实现，别的时间复杂度都是 O(n)，可以通过。

破防记录

环形数组一定要开两倍空间！！