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

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

P3396 哈希冲突

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


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

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

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

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

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

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;
}