洛谷 P3396 哈希冲突（根号算法 分块）

P3396 哈希冲突

题目链接
从这篇博客来做的这道题


分析：
看到这个题的数据范围是有点懵，这能怎么做啊？
先看暴力 $O(n^2)$ ，

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

如果我们做预处理的话，$ans[p][x]$ ，$\%p$ 时余数是 $x$ 的位置的和，这样复杂度还是 $O(n^2)$，查询 $O(1)$，会爆炸
然后要降复杂度吧，这里就要说到神奇的根号算法了（也不知道是不是叫这个名），分块
预处理 $[1,\sqrt{n}]$ 范围的模数 $p$

for (int i = 1; i <= n; i++)for (int j = 1; j <= sqrt(n); j++) //枚举模数pans[j][i%j] += value[i];

这样就能得到模数 $p\le \sqrt{n}$ 的所有余数 $x$ 的答案了，而且复杂度为 $O(n\sqrt{n})$，完全可以接受的
若模数 $p>\sqrt{n}$ ，那么余数为 $x$ 的位置不超过 $\sqrt{n}$ 个，同样复杂度小于 $O(\sqrt{n})$
修改时，更新 $x$ 位置对 $\%p$ 的答案，范围也是模数p的范围 $[1,\sqrt{n}]$，修改的复杂度$O(\sqrt{n})$
所以总的复杂度就是 $O(n\sqrt{n})$

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 150005; //sqrt(150000)=387.3
int n, m;
int a[N];
int b[400][400]; //b[p][x] %p意义下余数是x的位置的和
int main()
{ios::sync_with_stdio(false), cin.tie(nullptr);cin >> n >> m;int sq = sqrt(n);for (int i = 1; i <= n; i++){cin >> a[i];for (int j = 1; j <= sq; j++) // %j 意义下余数是 i%j 的数的和, %数大于sqrt(n)直接求就OK{b[j][i % j] += a[i];}}while (m--){string s;int x, y;cin >> s >> x >> y;if (s[0] == 'A'){if (x <= sq){cout << b[x][y] << endl;}else{int ans = 0;for (int i = y; i <= n; i += x){ans += a[i];}cout << ans << endl;}}else{for (int i = 1; i <= sq; i++) // a[x]位置对所有%数更新{b[i][x % i] += y - a[x];}a[x] = y;}}return 0;
}