洛谷 P3396 哈希冲突 分块思想

https://www.luogu.com.cn/problem/P3396

思路：先考虑暴力怎么做，用$ans[i][j]$记录在$modi$的情况下第$j$组的答案，显然我们在可以$O(n^2)$的时间复杂度下预处理出来，空间复杂度也是$O(n^2)$的，肯定不行。那么我们考虑折中一下，即预处理出$\sqrt{n}$的所有情况，也就是说预处理出$ans[1\dots \sqrt{n}]$，时间复杂度和空间复杂度都降到了$O(n\sqrt{n})$。当询问的$x<=\sqrt{n}$时，我们可以直接输出，否则就暴力计算答案，因为$x>\sqrt{n}$，所以这次暴力的复杂度为$O(\sqrt{n})$，也是可行的。最后我们考虑修改的复杂度，因为仅仅预处理出了$\sqrt{n}$的情况，所以修改的复杂度也是$O(\sqrt{n})$。那么这题就可以过掉了。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;const int maxn=2e5+5;int ans[500][500];//ans[i][j] mod i时 j池内数的总和
int a[maxn];int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int dis=sqrt(n);for(int i=1;i<=n;i++)for(int j=1;j<=dis;j++)ans[j][i%j]+=a[i];char ch;int x,y;while(m--){cin>>ch;scanf("%d%d",&x,&y);if(ch=='A'){if(x<=dis)printf("%d\n",ans[x][y]);else{int sum=0;for(int i=y;i<=n;i+=x)sum+=a[i];printf("%d\n",sum);}}else{for(int i=1;i<=dis;i++)ans[i][x%i]+=y-a[x];a[x]=y;}}return 0;
}