题解 P3396 【哈希冲突】
阮行止
2016-09-25 19:07:20
这是一道论文题。集训队论文《根号算法——不只是分块》。
首先,题目要我们求的东西,就是下面的代码:
```cpp
for(i=k;i<=n;i+=p)
ans+=value[i];
```
即:从 k开始,每隔p个数取一个数,求它们的和。
这个算法的复杂度是$O(n^2)$的。
令答案为$ans[p][k]$,表示模数是p,余数是k.
那么,对于第i个数,如何处理它对ans的贡献呢?
```cpp
for(p=1;p<=n;p++) //枚举模数
ans[p][i%p]+=value[i]; //处理对应的贡献
```
这样看上去很妙的样子,然而$O(n^2)$的预处理, $O(1)$询问,空间复杂度还是
$O(n^2)$的
所以我们很自然地想到:只处理$[1,\sqrt{n}]$以内的p
这样的话,令 $size=\sqrt{n}$,则可以这样预处理:
```cpp
for(p=1;p<=size;p++) //只枚举[1,size]中的
ans[p][i%p]+=value[] //处理对应的贡献
```
于是预处理的复杂度降到了 $O(n\sqrt{n})$.
接着考虑询问。如果询问的p<size ,那显然可以$O(1)$给出回答。
如果p超过size,我们就暴力统计并回答。因为 $p>\sqrt{n}$,所以少于$\sqrt{n}$个数对答案有贡献。所以对于 $p>\sqrt{n}$,暴力统计的复杂度是 $O(\sqrt{n})$..
接着考虑修改。显然我们把p<size的值全都更新一遍就行。复杂度也是 $O(\sqrt{n})$.
```cpp
void change(int i,int v) //将value[i]改为v
{
for(p=1;p<=size;p++)
ans[p][i%p]=ans[p][i%p]-value[i]+v; //更新答案
value[i]=v; //更新value数组
}
```
这样,我们就在$O((m+n)\sqrt{n})$.的时间内完成了任务