【LuoguP3396】哈希冲突
题目链接: https://www.luogu.org/problemnew/show/P3396
前言
话说快暑假了…但是好像没有几天假期啊。
然后期末考试之际做了找到题，发现暴力好像都能用分块优化。
分析
读完题目，发现想不到任何复杂度较低思路。对于几乎不接触分块的我，数据范围似乎没有什么用。
然后就打开了题解，才知道可以根号算法（不指分块），不过我统一把用sqrt函数的解法都叫做分块。
暴力的复杂度大概是$ O(mn) $ ，每次查询我们都需要$ O(n) $ 来遍历数组，修改是$ O(1) $。如果预处理的话那更玄学，每次查询时$ O(1) $，而修改是$ O(n^2) $ ，那么很有可能变成$ O(n^2m) $算法。
所以考虑只预处理$ \sqrt{n} $的模数，复杂度为$ O(n \sqrt{n}) $。
对于查询，如果查询的模数不超过$ \sqrt{n} $那么可以直接输出答案。如果模数超过$ \sqrt{n} $，我们只需要枚举模$ p $后的结果，把他们加起来，那么复杂度仍为$ \frac{n}{\sqrt{n}} = \sqrt{n} $。
对于修改，与预处理类似，还是只修改$ \sqrt{n} $的模数，由于只是单点修改，所以少了一层循环，那么复杂度为$ O(\sqrt{n}) $。
总复杂度最大是$ O((m + n)\sqrt{n}) $，然后就可以写代码了，代码极为简单，感觉像是暴力。
代码
1 | #include <iostream> |
后记
因为之前根号算法做比较少，而这道题给我很大的启示，以后一些只能想到暴力的题可以尝试使用根号来优化。
听说这题不用根号，而使用1/3次方作为块的大小效率更高。但是不会证明，而且复杂度比较玄学，可能只适用这一道题的数据吧。