当前位置：首页 > news >正文

分散层叠

news 2026/3/26 18:50:11

其实并不是什么神秘的东西，而且相当不适用，原因是在某些问题下虽然理论最优但常数极大。

P6466 分散层叠算法(Fractional Cascading)

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

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

若后继不存在，则定义为 \(0\)。

对于 \(100\%\) 的数据，\(1 \leq k\leq 100\)，\(2\leq n\leq 10^4\)，\(q\leq 5\times 10^5\)

先考虑只有两个序列 \(a,b\) 的情况，我们可以把它们合成一个序列 \(c\) 然后在这个序列上二分。

找到了在 \(c\) 中的后继后，我们记它为 \(c_i\)，我们考虑对序列 \(c\) 预处理出每个位置后首个在序列中出现的来自 \(a\)，\(b\) 序列的数。

这样我们就可以 \(O(n)\) 预处理，然后每次只需要一次二分。

然后对于多序列的情况，这时我们假如直接合到一个序列中，序列长度是 \(nk\)，做法会退化至 \(O(nk^2)\)。

我们考虑嵌套上边的做法，我们先将数组 \(a_1,a_2\) 合并成序列 \(b_1\)，对于序列 \(b\) 我们相邻两个数只保留一个，这样序列长度就是 \(n\)，然后我们在根据二分结果查找是就需要跳两次。

我们考虑再讲 \(b_1\) 与 \(a_3\) 合并成 \(b_2\)，依次重复这样的操作我们就能得到 \(b_{k-1}\)。

最终我们只需要二分一次，然后顺次推出每个序列的答案，这样复杂度降至单次 \(O(\log n+k)\)。

P5356 [Ynoi Easy Round 2017] 由乃打扑克

所以她出了一个数据结构题。

给你一个长为 \(n\) 的序列 \(a\)，需要支持 \(m\) 次操作，操作有两种：

查询区间 \([l,r]\) 的第 \(k\) 小值。
区间 \([l,r]\) 加上 \(k\)。

\(1\leq l\leq r \leq n\leq 10^5\)，\(1 \leq m \leq 10^5\)，\(-2\times 10^4\leq a_i, k\leq 2\times 10^4\)，\(opt \in \{1, 2\}\)。

考虑朴素分块，取块长为 \(B\)，每个块内维护块内数之间的升序排列。

对于修改操作，复杂度 \(O(B+\frac n B)\)，对于查询，我们先将两边散块归并，然后二分答案，复杂度 \(O(\log V\log B+\frac {n\log B\log V} B)\)，取 \(B=\sqrt {n\log V}\) 即可做到 \(O(n \sqrt n \log V)\)，注意 \(\log\) 在外边。

我们考虑分散层叠优化，具体的，我们用线段树维护块之间的分散层叠结构，块的升序排列上层维护对于这 \(\frac n B\) 个块的线段树，对于线段树每个节点，我们维护左右两个儿子各取排列的 \(\frac 1 3\) 的归并。

对于修改，散块的复杂度是 \(O(B)\)，在线段树上，复杂度是 \(O(B+\frac 2 3 B+\frac 4 9 B+\dots)≈O(B)\)，于是修改复杂度降至 \(O(B)\)。

对于查询，我们复杂度变为 \(O(\log V B+\log V\log B)\)，取 \(B=\sqrt {n\log V}\) 就能做到 \(O(n\sqrt {n \log V})\)。