分散层叠

这是我们原神的实机图片。

主要参考2020年集训队论文《浅谈利用分散层叠算法对经典分块问题的优化》，如果看不懂可以去看这个（然后你发现竟然完全相同，真是原原又神神啊）

看到很多次了，不学不行啊！原神！

2077.12.19米哈游面试题T1

题面的意思就是给你 \(k\) 个序列，然后 \(Q\) 次询问，每次问序列中的后继在什么位置，要求询问强制在线。

有一个原神算法就是枚举每个序列然后直接二分，单次 \(k\log n\)，听着就很原神。

我们再来考虑一个野蛮一点的算法

我们在二分次数上做文章，考虑把所有序列全部拼在一起，然后进行一手二分。

但是这样只能找到一个值，什么也找不到，所以对于每个数我预处理出他们在每个序列上的后继，利用单调性可以做到 \(O(nk)\)，非常帅气的算法，但是空间复杂度接受不了，存不下（唉，谁叫你不留空间）

那我们干脆再弱智一点，来到原神的领域，考虑把这个大序列掰成 \(n\) 个，因为我们只关心我们的下一个是怎么样对吧，所以我们现在设 \(M_i\) 表示 \(A_i\) 与 \(A_{i+1}\) 的并，再对每个数记录这个数在第 \(i\) 个序列和第 \(i+1\) 个序列中的后继分别在哪。

可惜没法做，因为这玩意出了所有的话做第二轮的时候判断标准就会从两个序列一起判跌落成只判一个序列，再往后可谓是一点准确度也没有了，如果要判就必须拿指针在另一个序列上动，如果保留指针离线的话可以做（不过都有这种程度了为什么不直接枚举），可惜强制在线，当然也可以倒过来存储所有的，空间会炸。

于是我们就想怎么优化他，我们发现我们自己作死要引入下一个序列的全部，如果我每 \(d\) 个取一个呢？容易发现前一个序列二分出来来找人，误差不会超过 \(d\)，枚举误差内的数就行。

在板题中大家都取 \(d=2\)，因为这样做了之后一个序列的长度肯定不会超过 \(2n\)，具体原因自己分析。

这就是分散层叠板子。

考虑一般形式，给你一个 DAG，每个点代表的是一个序列，每次在 DAG 上面抽一条链出来问你他的所有后继，对于这种你考虑把她的最大出度 \(k\) 拿下，比如例题 \(k=1\)，我们选择 \(d\) 是没有啥特殊要求的，要求就是 \(d\) 不能超过 \(\frac{n}{k}\)，原因显然，最后时间复杂度的话，考虑第一次的 二分，那个二分是 \(O(\log n)\) 的后面做了序列个数次枚举就做好了。

因为 \(d\) 是常数所以不考虑他但是做得时候扰动的常数如果很大还是要计算。。

分散层叠在分块上的运用。

这玩意看着就很分块吧，有分散层叠不用王八蛋！