「Daniel13265 的公开赛」题解【集合】

· · 题解

这是「Daniel13265 的公开赛」的官方题解。

测试点 1,2,3

留给所有普通权值线段树以及常数正常的平衡树。

测试点 4,5

留给常数优秀的平衡树。

测试点 6,7

留给常数极其优秀的平衡树（怀疑？）与各种乱搞。

标程是基于权值线段树的乱搞。

首先用权值数组存储一个数是否在集合中，然后将它的每一个位置看作一个叶子结点建立一棵完全 \omega 叉树，每一个非叶子结点压位存储它的哪些子结点所代表的值域区间有非零值。那么操作 1,2 与询问 3,4,5,6 都是很简单的了，接下来考虑询问 7,8。

这里只讨论询问 7，因为询问 8 同理。首先如果 x=0 则返回 -1；否则考虑从树的底端代表 x 的结点向上查询。假设查询到了当前的非根结点，如果该结点父结点在当前结点或者左侧的儿子结点有非零值，说明找到了所需的小于 x 的值，于是向下不断靠右求出具体位置；如果没有，说明该结点的父结点所代表的值域区间还没有找到，于是继续向上查找即可。到达了根结点还没有找到就说明集合中没有小于 x 的数，返回 -1 即可。

这个数据结构的总空间复杂度为

\sum_{k=1}^{\log_\omega n}\mathcal O\left(\frac n{\omega^k}\right)=\mathcal O\left(\frac n\omega\right)

明显，单次 1,2 操作与询问 3,4,7,8 的时间复杂度都是 \mathcal O\left(\log_\omega n\right)，而询问 5,6 的时间复杂度是 \mathcal O(1) 的。

实际上，如果取 \omega=2^6,n=2^{30}，那么时间复杂度中

\log_\omega n=\log_{2^6}2^{30}=5

甚至可以看作为常数。常数最大的为询问 7,8，约为操作 1,2 与询问 3,4 的常数的 2 倍。标称在测试点 4,5 与测试点 6,7 之间体现出来的接近一半的时间差就在于数据中询问 7,8 的个数差。

当数的值域 n 与操作个数 m 满足 n\le m\cdot\omega 时，这个数据结构可以代替 std::set<unsigned int, std::less<unsigned int>, std::allocator<unsigned int>>（C++17 前）std::pmr::set<unsigned int, std::less<unsigned int>, std::pmr::polymorphic_allocator<unsigned int>>（C++17 起），因为前者的时间复杂度和空间复杂度都优秀于后者。