分散层叠算法(Fractional Cascading)

· · 题解

考虑经典问题：

给出 k 个长度为 n 的有序数组。

现在有 q 个查询 : 给出数 x，分别求出每个数组中大于等于 x 的最小的数(非严格后继)。

强制在线。

首先，我们有经典二分算法，可以在 O(nk+qk\log n) 的复杂度内做，但是 qk\log n 实在太大，无法接受。

考虑一开始将所有数排序，容易用多路归并算法做到 O(nk\log k)，那么为每个数附上颜色以表示其属于哪个序列。

那么我们在查询时可以先二分一次，这样我们我们就将问题转化成了要查询某个位置之后每个颜色的最前的出现位置，容易做到 O(nk^2)。

因此总复杂度可以做到 O(nk^2+q(k+\log(nk)))。

你发现这个还是很唐，我们考虑详细看一下归并过程。

我们考虑从下向上归并，每次选出当前偶数位的数与上一层进行归并，在归并时记下自己在当前这一层的后继是谁，在下面的归并序列的位置。

那么我们考虑查询，容易发现上一层到下一层的位置与后继之间的差不会超过 1。

考虑前面处理的复杂度，每一层向上走时长度都会除 2，那么归并复杂度是 O(nk) 的。

那么总复杂度为 O(nk+q(k+\log n))。

注意到我们显然可以调整每一层的序列的长度，设选其中 \frac{1}{p} 的数，那么复杂度为 O(\frac{nk}{p}+q(k\log p+\log n))。

但其实，对此的问题我们有更平凡的做法。

考虑原来的归并做法，注意到不可行的原因在于我们要处理出所有颜色的答案，但这是不必要的，我们可以设 nxt_i 表示 i 后面颜色 i \bmod k+1 的位置。

那么我们二分到一个位置 pos 之后，只需查询 nxt_{pos},nxt_{pos+1} \dots nxt_{pos+k-1}，注意到在 pos+k 之后的一定可以被找到，只需枚举 pos \dots pos+k-1 即可。

那么总复杂度为 O(nk\log k+q(k+\log (nk)))。

这个显然也可以模仿分散层叠进行均摊，只需让 p 的倍数的位置丢进去即可，当然每次查询还是需要多一个 \log p，复杂度为 O(\frac{nk\log k}{p}+q(k\log p+\log (nk)))。

当然的，可以用基数排序消掉预处理的 log。