10.3 闲话-分散层叠
这个东西好像没什么用,但是好像有有些用。
先看这么个问题:
给定 \(k\) 个长度为 \(n\) 的序列,\(m\) 次询问,每次询问 \(x\) 在 \(k\) 个序列中的后继的异或和,强制在线。
这东西有个显然的 \(O(mk\log n)\) 做法,但是我们可以寻求更优秀的算法。
分散层叠维护的就是这么个东西。
分散层叠需要维护一个数组 \(M_{i,j}\) 其中有三个值 \(\{val, now, nxt\}\) 分别表示值,该序列后继位置,\(M_{i+1}\) 中后继位置。
但是这时直接跳肯定假了,为啥?
因为前面可能还有合法的点呢,那么可以每隔一个将 \(M_{i+1}\) 中的元素插入 \(M_{i}\) 中,这是维护的 \(nxt\) 就是这写插入点中的后继位置了。
这时跳下去竟然合法点只有 \(nxt, nxt-1\) 两个点,为啥?
因为 \(nxt - 2\) 一定在 \(M_{i}\) 可是我们没有找到它,那么它就一定不是后继。
使用归并排序维护,查询先二分出 \(M_1\) 的位置。
复杂度 \(O(m(k+\log n))\),空间复杂度 \(O(2n)\)。
这个分散层叠十分深刻的一点是它其实维护的是一个 \(DAG\) 结构,所以支持 \(DAG\) 上的链查询。
还有就是为什么要隔一个插一个,其实可以隔 \(p\) 个,这是也是没有问题的,可以做到时空复杂度平衡。
这东西可以做一些大分块,比如第十分块加强版。
可以分块后每个块维护分散层叠,能做到 \(O(n\sqrt{n\log n})\),线段树底层分块加分散层叠做到 \(O(n\sqrt n)\)。
修改暴力重构就行。