专栏文章

题解：CF2066E Tropical Season

RRotating_Lines
CF2066E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minih3o9
此快照首次捕获于
2025/12/02 02:57
3 个月前
此快照最后确认于
2025/12/02 02:57
3 个月前
查看原文

题解

考虑如果有两个相同重量的桶那么我们就能比较他们，并且比较了之后这两个桶里面的水我们就能自由调动了。假设我们现在有 xx 的水能够自由调动，考虑如何拓展。思考不难发现有两种情况：
  1. x≥aix\ge a_i，我们能够分出恰好 aia_i 的水去比较，于是 aia_i 也能用了。
  2. ai<aj,ai+x≥aja_i<a_j,a_i+x\ge a_j，于是我们考虑给少的分一些水然后就可以比较两个桶了，然后这两个桶的水就都能用了。
于是我们给 aia_i 排序，从小到大考虑水，每次先找到两个相同的然后开始拓展。容易得到单次 O(n)\mathcal O(n) 的做法。现在考虑优化。
可以发现每次拓展了一个新的桶之后我们又可以多拓展很多桶，并且考虑上述两种拓展的方法其 xx 的增长都是 ≥2ai\ge 2a_i 的。于是我们考虑倍增值域，更进一步，我们能够联想到一个东西，叫做倍增值域分块。现在考虑分块后如何拓展。
对于一个 2k≤ai<2k+12^k\le a_i<2^{k+1} 的桶，如果我们能够拓展出它，那么我们一定能够拓展整个块内的元素，证明上面已经提过就不赘述了。于是每次我们从小到大去扫这 O(log⁡)\mathcal O(\log) 个块，分别去看两种方式是否存在一种能够拓展这个块内的一个元素即可。
具体的，我们考虑对于每个块维护两个 multiset 分别记录 aia_i 和 Δ=ai+1−ai\Delta=a_{i+1}-a_i，然后每次拿块内最小的去和 xx 进行比较即可。注意块间的 Δ\Delta 不要算漏即可。时间复杂度 O(nlog⁡V)\mathcal O(n\log V)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...