是由 这个题 引起的疑问。
好像各种资料上都说 gp_hash_table 跑得比 cc_hash_table 快一些,尤其是在随机数据下,但是这题中我使用了哈希表维护当前有值的位置,我认为都是 O(1)\mathcal{O}(1)O(1) 操作的,但是实际上两者效率差别极大,使用 gp_hash_table 完全跑不过,但是我改成 使用 cc_hash_table 就能跑过去,(不过这种做法只能在 loj 神机上通过,洛谷上无论写哪个都会 T,但是仍然是 cc_hash_table 可以跑过更多测试点)。这是为什么呢?是因为 gp_hash_table 被卡了吗?
遍历 cc_hash_table 的复杂度究竟是多少呢?比如我的写法里面只保留了值不为 000 的位置,这些位置至多 n\sqrt nn 个,那我遍历的复杂度是 O(size)\mathcal{O}(size)O(size) 的还是要多一个 log\loglog 呢?
还有这个题是不是过于卡常了。。。