自动搬运

查看原文

来自洛谷，原作者为

	gxy001 ......

搬运于2025-08-24 22:34:04，当前版本为作者最后更新于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)$，并且要恰好把儿子分成两部分。

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