自动搬运

查看原文

来自洛谷，原作者为

	阮行止 算法+网络安全研究者，致力于推动 OI 教育的进步

搬运于2025-08-24 21:48:33，当前版本为作者最后更新于2016-09-25 19:07:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一道论文题。集训队论文《根号算法——不只是分块》。

首先，题目要我们求的东西，就是下面的代码：

for(i=k;i<=n;i+=p)
    ans+=value[i];

即：从 k开始，每隔p个数取一个数，求它们的和。

这个算法的复杂度是$O(n^2)$的。

令答案为$ans[p][k]$，表示模数是p，余数是k.

那么，对于第i个数，如何处理它对ans的贡献呢？

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}$，则可以这样预处理：

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})$.

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})$.的时间内完成了任务