题解 P6466 【分散层叠算法(Fractional Cascading)】

AThousandSuns · 2020-11-27 16:42:29 · 题解

在我的博客看效果更佳：点这里

本文主要参考 IOI 2020 中国国家候选队论文《浅谈利用分散层叠算法对经典分块问题的优化》。

本文仅描述了该算法的基本思想及实现，更深入的理论及应用请在论文中查阅。（或者哪天我有闲心了来写

本文提供的代码并没有经过精细实现，同时依赖于模板题的一些特殊限制，所以不推荐作为模板使用，也不保证在一般情况下仍然有正确性。

分散层叠算法可以解决下述问题：

• 给定 k 个有序序列，长度的和为 n。q 次询问，每次给定数 x，求出其在每个序列的后继。下文中认为，这个后继是非严格的。

对于 k=1 是一个经典的二分算法，可以做到 O(n)-O(\log n)。

这个算法做 k 次即有 O(n)-O(k\log\frac{n}{k}) 的复杂度。

另一种常见算法，是将这 k 个序列归并成一个长为 n 的序列，同时对于每个元素记录其后面第一个来自第 i 个序列的数是哪个。那么每次查询都可以在大序列中二分，通过在大序列的后继记录的信息得到在每个序列的后继。

这个算法的复杂度为 O(nk)-O(k+\log n)，同时空间复杂度也是 O(nk)。

分散层叠算法可以 O(n)-O(k+\log n) 解决这个问题，且空间复杂度是 O(n)。

我们将一开始给出的第 i 个序列叫做 L_i。然后预处理另外 k 个有序序列 M_i。