Luogu P3396 哈希冲突

奇迹硬壳

看了不会做,只会暴力。for (int i = k; i <= n; i += p) ans += value[i];

一看题解,wdnmd真就暴力啊都

预处理$p \le \sqrt{n}$的答案,$f_{p, d}$表示模p余d的和。对于$p > \sqrt{n}$的答案,直接暴力求。对于所有修改,直接暴力改。

考虑这样做复杂度为什么是对的。首先预处理的复杂度是$O(n\sqrt{n})$,暴力查找时,由于$p > \sqrt{n}$,所以有贡献的数少于$\sqrt{n}$,暴力查找的复杂度是$O(\sqrt{n})$。修改只修改$p\le \sqrt{n}$的答案,也是$O(\sqrt{n})$的,总复杂度是$O((m + n)\sqrt{n})$的。

根号算法看起来好像非常暴力,可是复杂度很科学。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>

const int N = 150000, B = 300;
int n, m, v[N + 233], qwq[B + 233][B + 233];

signed main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", v + i);
for (int j = 1; j <= B; ++j) qwq[j][i % j] += v[i];
}
while (m--) {
char op[20];
int x, y;
scanf("%s%d%d", op, &x, &y);
if (op[0] == 'A') {
if (x <= B) {
printf("%d\n", qwq[x][y % x]);
} else {
int res = 0;
for (int i = y; i <= n; i += x) res += v[i];
printf("%d\n", res);
}
} else {
for (int i = 1; i <= B; ++i) qwq[i][x % i] += y - v[x];
v[x] = y;
}
}
return 0;
}
# 分块

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×