P7897 [Ynoi2006] wcirq

gxy001 · 2021-10-06 18:07:20 · 题解

我们想到用平衡树维护这个东西，但常见的平衡树都是均摊和期望的，所以我们考虑固定每一层的集合大小和深度，便于分析复杂度。

我们构造一个 Leafy Tree，第 i 层的节点对应的集合大小为 [4^{i-1},4^i)，叶子（第 0 层）节点大小为 1。

单次插入的操作次数就是深度，也就是 11 的样子。

一个节点最多有 15 个儿子，所以查询的操作次数大概在深度乘二倍的儿子数左右，常数很小，应该能控制在 256 次内。

现在的问题就是插入后如果一个节点集合大小超过了上界，如何处理。

考虑分裂，但是分裂后的集合需要重新维护，我们如果暴力插入的话，均摊复杂度显然是正确的，但我们要保证 Worst Case，所以不能暴力。

我们认为一个集合大小等于 3\times 4^{i-1} 的节点是即将分裂的，这样的节点再进行 4^{i-1} 次插入就会分裂，我们维护它分裂出的两个集合，每进行一次插入就向分裂后的集合进行四次插入，这样当它分裂时，我们正好维护出了它分裂出的两个集合，这里有一点小细节，就是我们要保证分裂出的集合大小在 [4^{i-1},4^i)，并且要恰好把儿子分成两部分。

非常好实现，就不给代码了。