CF1732D2 Balance (Hard version) 题解

建议先阅读 $\textbf{Easy Ver.}$ 题解。

前情提要：我不会做这题。所以我用了一个奇奇怪怪的时间复杂度极劣的做法通过了这个题。如果要学习正解建议跳过这篇题解。如果用这个做法的话这题最多蓝（

在简单版本中，没有删除操作，因此对于同一个 $k$ 的答案是单调的，可以直接暴力维护；但是在困难版本中，删除操作导致某一些 $k$ 的值可能会突然反弹回去。而如果暴力枚举所有因数然后把值清空，又有可能陷入删除 - 添加 - 删除 - 添加 - …… 的困境，导致时间复杂度很劣。

那么应该如何避免这种情况呢？简单粗暴的算法肯定不可行了，因此考虑一些奇奇怪怪的做法：设立一个阈值 $P$，对于加入操作还是直接加入一个 set 中，删除操作则记录当前所有被删除的元素。查询操作仍然是先暴力跳，然后枚举所有被删除的元素 check 是否用这个元素会合法且让当前答案更优。为了保证时间复杂度，若某一次操作后删除元素集合的元素数量 $>P$，则直接暴力重构当前集合。

继续用 map/set 系列平衡树相关 STL 时间复杂度多个 $\log$，因此考虑用 umap/uset 加 splitmix64 hash，时间复杂度为 $O(qP+\frac qPq\log q)$，根号平衡即 $qP=\frac qPq\log q$，解得 $P=\sqrt{q\log q}$ 时等号成立，此时根号平衡。因此总时间复杂度为 $O(q\sqrt{q\log q}+\frac{q^2\log q}{\sqrt{q\log q}})$，可以通过。

顺便提一下做这题的时候我踩过的坑：

• 如果你 wa on test $16$，那么请检查如果你缓存了删除信息，但是又在没有 flush 暴力重构删除信息之前插入了元素，那么此时需要特殊处理，将该元素从缓存的信息中删除（撤销）。
• 如果你 tle on test $60$，那么你要么是被卡常了，要么是因为你把缓存的删除信息用 set 存储了。事实证明因为缓存信息量很少所以用 vector 存储该信息要远远快于 set 存储，差距大约在 $5\sim 6$ 倍左右。
• 事实证明如果你块长真的取了 $\sqrt{q\log q}$ 会 tle on test $60$，大概是跑 $4\sim 5$ 秒的样子。把块长取 $\sqrt q$ 只会更慢（$25$ 秒左右）。如果把块长取为 $\lfloor 2.5\times\sqrt{q\log q}\rfloor$ test $60$ 会跑 $2$ 秒不到，但是会 tle on test $67$。
• 如果你块长取 $\lfloor\frac\pi2\sqrt{q\log q}\rfloor$ 那么 test $60,67$ 经过极限卡常都能过，但是会 tle on test $82$，差不多是 $3.2\sim 3.5$ 秒的时间过不去。
• 只差一点了，能不能再接再厉？启动指令集！vector 就算开了 Ofast 也跑不过普通的数组，用数组替换，现在是 $3.1$ 秒，真的就只有那么一步了！
• 众所周知有个东西叫 fread 快读，对应的我们还可以发现有一个东西叫 fwrite 快写。把这个应用于我们的程序。然后我们还知道 CF 中 C++17,20,23 的速度应该是 $20<17<23$ 的，所以用 C++20 提交代码，可以获得 $3.05$ 秒的好成绩！
• 真的就过不去了吗？众所周知还有个东西叫平板电视库，调用该库中的 gp_hash_table 要远远快于 unordered_map，于是把所有 umap 都改成 gp_hash_table，这样 test $60$ 只会跑 $1.3$ 秒，test $67$ 只会跑 $0.15$ 秒。但是这样会被专门卡 gp_hash_table 的 test $90$ 给卡到 $11$ 秒（值得一提的是，test $69$ 也跑不过去）。
• 发现如果没有修改操作，然后询问的值已经被询问过了，那么可以直接调用上一次的询问。然后把 buffer 调大一点，可以获得 $3015$ 毫秒的好成绩。
• 真的没法再优化了啊！考虑继续试块长，最终发现若 $P=\lfloor 1.56\times \sqrt{q\log_2q}\rfloor$，则可以以 $2.95$ 秒的成绩惊险通过。（实际上是 $2952$ 毫秒）。

最后放一下代码，使用了可爱 aimat 姐姐的一些板子。代码。