【学习笔记】分散层叠

前言

真的真的是群除我会/ll/ll/ll

本学习笔记基本参考：
【IOI2020 论文集】蒋明润，浅谈利用分散层叠算法对经典分块问题的优化。

简介

英文名是 $\text{Fractional Cascading}$，觉得很好看（

其用处是对于一个固定的 $x$，找到 $x$ 在 $k$ 个不同有序数列中的后继分别是谁。

思想

对于这个问题，有两种解决方法：

最简单的就是在每个序列中分别二分，时间复杂度 $\mathcal{O}(k\log n)$，空间复杂度 $\mathcal{O}(n)$。

另一种方法就是将 $k$ 个序列先进行归并，记录每一个位置之后的，属于每一个序列的最近位置。这样时间复杂度是 $\mathcal{O}(k+\log n)$，但空间复杂度是 $\mathcal{O}(nk)$。

而分散层叠可以同时达到上述的较优时空复杂度。

其大概思想是构造 $k$ 个序列，第 $i$ 个称作 $M_i$。第 $M_i$ 个序列由 $a_i$ 与 $M_{i+1}$ 的一半归并而成。“一半”的意思是：从第二个元素开始，隔一个元素选一个。

这样的好处是什么呢？注意到 $M_i$ 的长度可以表示为：

$$ |a_i|+\dfrac{1}{2}|a_{i+1}|+\dfrac{1}{4}|a_{i+2}|\cdots=\mathcal{O}(n) $$

所以这样的空间复杂度就是 $\mathcal{O}(n)$ 的了。

如何查询？对于 $M_i$ 中的任意一个元素，记录三个值 $(v,l,p)$，分别表示这个元素的“确切值”，“$\ge$ 这个值的第一个在 $a_i$ 中的元素是 $a_{i,l}$”，“$\ge$ 这个值的第一个在 $M_{i+1}$ 中的元素是 $M_{i+1,p}$”，此处 $p$ 一定是偶数（因为是隔一个取一个）。

假设现在已经得到了在 $M_i$ 中 $x$ 的位置，则可以立马得到在 $a_i$ 中 $x$ 的后继是谁。如何转移到下一个序列呢？注意到我们可以使用 $p$，移动到 $M_{i+1}$ 的某一个偶数位置。

但这可能会出错，因为在 $M_i$ 中我们只考虑了 $M_{i+1}$ 的偶数位置，却丢失了奇数位置。因此，每次只需要再检查一下当前 $p$ 之前的那个奇数位置 $p-1$ 是否也 $\ge x$，如果是，则 $p-1$ 才是 $M_{i+1}$ 中真正的后继。

于是，我们只要在 $M_1$ 中进行一次二分，后面的就都可以 $\mathcal{O}(1)$ 移动到了。