概述
Fractional Cascading 算法，国内多译为“分散层叠算法”，用于解决在多个有序序列中的查找问题，单次复杂度为线性。Fractional Cascading 算法思想与跳表类似。
此算法思想可以用在一些图论题中
问题
给出 $k$ 个长度为 $n$ 的有序数组 $a_{i, j}$。
现在有 $q$ 个查询 : 给出数 $x$，分别求出每个数组中大于等于 $x$ 的最小的数，要求在线。
使用类似牛顿迭代的查找方式可以做到期望 $\Theta\left(n \log \log n\right)$，但可以容易地被卡成 $\mathcal O\left(n^2\right)$。
算法
Fractional Cascading 的本质就是避免一些重复的二分操作。
维护数组 $b_{i, j}$，它类似于一个跳表结构。
从最底层开始生成，一层的每个数都有 $P$ 的概率在上一层保留。同时需要对每个数记录 $now$ 和 $next$ 两个量，$now$ 表示 $b_{i, j}$ 对应到 $a_{i, j}$ 中的位置（这个值在 $a$ 中不一定有，对应是指当访问到 $b_{i, j}$ 时应该跳转到 $a$ 中的位置），$next$ 表示 $b_{i, j}$ 对应到下一层 $b$ 数组的位置。
可能有些难以理解，用样例作解释（$b$ 数组中 $\left[x, y, z\right]$ 表示 $b_{i, j}$ 的值为 $x$，$now = y$，$next = z$），为了方便理解，这里 $P$ 取 $\frac12$，并以一个隔一个的频率上提：
a[1] = { 1, 4, 6, 7, 10, 20 }
a[2] = { 2, 3, 8, 11, 14, 18 }
a[3] = { 5, 9, 12, 13, 15, 17 }
b[3] = { [5, 1, 0], [9，2, 0], [12，3, 0], [13, 4, 0], [15, 5, 0], [17, 6, 0] }
b[2] = { [2, 1, 2], [3, 2, 2], [8, 3, 2], [9, 4, 2], [11, 4, 4], [13, 5, 4], [14, 5, 6], [17, 6, 6], [18, 6, 6] }
b[1] = { [1, 1, 2], [3, 2, 2], [4, 2, 4], [6, 3, 4], [7, 4, 4], [9, 5, 4], [10, 5, 6], [13, 6, 6], [17, 6, 8], [20, 6, 8] }查找是只需要从第一层开始二分，每次顺着 $next$ 值向下一层查找即可。
单次查询期望时间复杂度为 $\Theta\left(\log n - k \log P\right)$。
期望空间复杂度为 $\Theta\left(k \cdot n\left(1 + P + P^2 + \cdots\right)\right) = \mathcal O\left(\dfrac{kn}{1 - P}\right)$。
取恰当的 $P$，平衡时空复杂度即可。
代码
// P = 0.5
struct LNode {
tp val, now, next;
LNode() = default;
LNode(tp _val, tp _now, tp _next) : val(_val), now(_now), next(_next) {}
bool operator<(LNode comp) const { return val < comp.val; }
};
void STRUGGLING([[maybe_unused]] lo TEST_NUMBER) {
tp n, k, q, d; bin >> n >> k >> q >> d;
vector a(k + 1, vector<tp>(n + 1, 0));
vector b(k + 1, vector<LNode>(n + 1));
for (tp i = 1; i <= k; ++i) {
for (tp j = 1; j <= n; ++j) bin >> a[i][j];
}
[&]() -> void {
mt19937 rng(58);
for (tp i = 1; i <= n; ++i) b[k][i] = LNode(a[k][i], i, 0);
for (tp i = k - 1; i >= 1; --i) {
for (tp j = 1; j <= n; ++j) b[i][j] = LNode(a[i][j], j, 0);
for (tp j = 1; j < b[i + 1].size(); ++j) {
if (rng() % 2 == 0) b[i].emplace_back(b[i + 1][j].val, 0, j);
}
stable_sort(FULL(b[i]));
for (tp j = 1; j < b[i].size(); ++j) {
if (b[i][j].next == 0) continue;
tp x = j - 1;
while (x >= 1 && b[i][x].next == 0) b[i][x--].next = b[i][j].next;
}
for (tp j = 1; j < b[i].size(); ++j) {
if (b[i][j].now == 0) continue;
tp x = j - 1;
while (x >= 1 && b[i][x].now == 0) b[i][x--].now = b[i][j].now;
}
for (tp j = 1; j < b[i].size(); ++j) {
if (b[i][j].now == 0) b[i][j].now = n + 1;
}
for (tp j = b[i].size() - 1; j >= 1; --j) {
if (b[i][j].next != 0) {
for (tp k = j + 1; k < b[i].size(); ++k) {
if (b[i][k].next == 0) b[i][k].next = b[i][j].next;
}
break;
}
}
}
}();
auto search = [&](tp x) {
tp l = 1, r = b[1].size() - 1, ret = 0, tar;
while (l <= r) {
tp mid = (l + r) / 2;
if (b[1][mid].val >= x) r = mid - 1;
else l = mid + 1;
}
if (l == b[1].size()) --l;
else ret ^= a[1][b[1][l].now];
tar = b[1][l].next;
for (tp i = 2; i <= k; ++i) {
while (tar >= 2 && b[i][tar - 1].val >= x) --tar;
while (b[i][tar].val < x && tar + 1 < b[i].size() && b[i][tar + 1].val >= x) ++tar;
while (tar + 1 < b[i].size() && b[i][tar + 1].val <= x) ++tar;
if (tar + 1 != b[i].size() || b[i][tar].val >= x) ret ^= a[i][b[i][tar].now];
tar = b[i][tar].next;
}
return ret;
};
tp lans = 0;
for (tp i = 1; i <= q; ++i) {
tp x = bin ^ lans;
lans = search(x);
if (i % d == 0) bin << lans << '\n';
}
}
void MIST() {
}