题解：CF2066E Tropical Season

Rotating_Lines · 2025-10-24 19:32:06 · 题解

题解

考虑如果有两个相同重量的桶那么我们就能比较他们，并且比较了之后这两个桶里面的水我们就能自由调动了。假设我们现在有 x 的水能够自由调动，考虑如何拓展。思考不难发现有两种情况：

于是我们给 a_i 排序，从小到大考虑水，每次先找到两个相同的然后开始拓展。容易得到单次 \mathcal O(n) 的做法。现在考虑优化。

可以发现每次拓展了一个新的桶之后我们又可以多拓展很多桶，并且考虑上述两种拓展的方法其 x 的增长都是 \ge 2a_i 的。于是我们考虑倍增值域，更进一步，我们能够联想到一个东西，叫做倍增值域分块。现在考虑分块后如何拓展。

对于一个 2^k\le a_i<2^{k+1} 的桶，如果我们能够拓展出它，那么我们一定能够拓展整个块内的元素，证明上面已经提过就不赘述了。于是每次我们从小到大去扫这 \mathcal O(\log) 个块，分别去看两种方式是否存在一种能够拓展这个块内的一个元素即可。

具体的，我们考虑对于每个块维护两个 multiset 分别记录 a_i 和 \Delta=a_{i+1}-a_i，然后每次拿块内最小的去和 x 进行比较即可。注意块间的 \Delta 不要算漏即可。时间复杂度 \mathcal O(n\log V)。