题目描述
https://www.luogu.com.cn/problem/P3396
简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $m$ 次操作，第一种操作修改一个 $a_i$ 的值，另一种操作给定 $k$ 和 $x$，求 $\sum_{i=1}^n[i\equiv x(\bmod k)]a_i$
$n,m\le 1.5\times 10^5$
Solution
我们同样考虑预处理答案
注意到当模数大于 $\sqrt n$ 时可以直接暴力
所以我们只需要存储模数小于 $\sqrt n$ 的答案，预处理的复杂度为 $O(n\sqrt n)$
修改时我们也只需要考虑改完之后对于模数小于 $\sqrt n$ 的答案的影响，可以直接暴力修改，复杂度是 $O(\sqrt n)$
总的时间复杂度为 $O((n+m)\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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include <iostream>
#include <cstdio>
#include <cmath>
#include <cctype>
#define maxn 150010
#define maxs 400
#define gc getchar
using namespace std;
int read() {
int x = 0; char c = gc();
while (!isdigit(c)) c = gc();
while (isdigit(c)) x = x * 10 + c - '0', c = gc();
return x;
}
int n, m, a[maxn];
int num, blo, d[maxs][maxs];
void init_blo() {
blo = sqrt(n); num = n / blo; if (n % blo) ++num;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= blo; ++j) d[i % j][j] += a[i];
}
int query(int p, int k) {
if (p > blo) {
int ans = 0;
for (int i = k; i <= n; i += p) ans += a[i];
return ans;
}
return d[k][p];
}
void update(int k, int v) {
for (int i = 1; i <= blo; ++i) d[k % i][i] += v - a[k];
a[k] = v;
}
inline void solve_1() {
int x = read(), y = read();
printf("%d\n", query(x, y));
}
inline void solve_2() {
int x = read(), y = read();
update(x, y);
}
int main() {
n = read(); m = read();
for (int i = 1; i <= n; ++i) a[i] = read();
init_blo();
for (int i = 1; i <= m; ++i) {
char s[5]; scanf("%s", s);
switch (s[0]) {
case 'A' : solve_1(); break;
case 'C' : solve_2(); break;
}
}
return 0;
}
|