考场上想出来的神秘做法，具体细节看注释。 时间复杂度：我不到啊 有没有佬能算出来 Code:

题目解析 我们考虑维护所有的为空的单元；对于「线性探测法」本质上就是找到 第一个大于等于 XXX 的空单元，若不存在这样的空单元，则寻找 第一个大于等于 000 的空单元。 那么我们可以考虑使用 std::set 来维护所有的 NNN 个空单元，并使用 std::map 来记录所有已经插入哈希表的元素分配到的位置即可。 时间复杂度：O(Qlog⁡N)\mathrm{O}(Q\log{N})O(QlogN)。 AC代码

这道题目考的是哈希，那肯定会卡哈希，所以我就不用 unordered_map 做了 本题插入的意思就是找到第一个内容为空的单元，如果直接暴力会被卡到 O(N)O(N)O(N)。 但是，众所又周知，线段树可以 O(log⁡N)O(\log N)O(logN) 找到第一个符合条件的点！ 那么，模拟，秒了。 诶等等，在样例的第 444 次操作中，由于前面没有空位，它探测到后面去了！ 没事，像合并石子一样，再复制一个拼接到后面就能当循环空间用了。