A2990. 哈希冲突
编程题
提高+/省选-
知识点
题目描述
众所周知，模数的 hash 会产生冲突。例如，如果模的数 $p=7$，那么 $4$ 和 $11$ 便冲突了。B 君对 hash 冲突很感兴趣。他会给出一个正整数序列 $\text{value}$。
自然，B 君会把这些数据存进 hash 池。第 $\text{value}_k$ 会被存进 $(k \bmod p)$ 这个池。这样就能造成很多冲突。
B 君会给定许多个 $p$ 和 $x$，询问在模 $p$ 时，$x$ 这个池内 **数的总和**。
另外，B 君会随时更改 $\text{value}_k$。每次更改立即生效。
保证 ${1\leq p<n}$。
自然，B 君会把这些数据存进 hash 池。第 $\text{value}_k$ 会被存进 $(k \bmod p)$ 这个池。这样就能造成很多冲突。
B 君会给定许多个 $p$ 和 $x$，询问在模 $p$ 时，$x$ 这个池内 **数的总和**。
另外，B 君会随时更改 $\text{value}_k$。每次更改立即生效。
保证 ${1\leq p<n}$。
输入格式
第一行，两个正整数 $n$, $m$，其中 $n$ 代表序列长度，$m$ 代表 B 君的操作次数。
第一行，$n$ 个正整数，代表初始序列。
接下来 $m$ 行，首先是一个字符 $\text{cmd}$，然后是两个整数 $x,y$。
- 若 $\text{cmd}=\text{A}$，则询问在模 $x$ 时，$y$ 池内 **数的总和**。
- 若 $\text{cmd}=\text{C}$，则将 $\text{value}_x$ 修改为 $y$。
第一行，$n$ 个正整数，代表初始序列。
接下来 $m$ 行，首先是一个字符 $\text{cmd}$，然后是两个整数 $x,y$。
- 若 $\text{cmd}=\text{A}$，则询问在模 $x$ 时，$y$ 池内 **数的总和**。
- 若 $\text{cmd}=\text{C}$，则将 $\text{value}_x$ 修改为 $y$。
输出格式
对于每个询问输出一个正整数，进行回答。
输入输出样例
输入 #1
10 5 1 2 3 4 5 6 7 8 9 10 A 2 1 C 1 20 A 3 1 C 5 1 A 5 0
输出 #1
25 41 11
说明/提示
#### 样例解释
#### 数据规模
对于 $10\%$的数据，有 $n\leq 1000$，$m\leq 1000$。
对于 $60\%$ 的数据，有 $n\leq 100000$，$m\leq 100000$。
对于 $100\%$ 的数据，有 $n\leq 150000$，$m\leq 150000$。
保证所有数据合法，且 $1\leq \mathrm{value}_i \leq 1000$。
A 2 1 的答案是 1+3+5+7+9=25。A 3 1 的答案是 20+4+7+10=41。A 5 0 的答案是 1+10=11。#### 数据规模
对于 $10\%$的数据，有 $n\leq 1000$，$m\leq 1000$。
对于 $60\%$ 的数据，有 $n\leq 100000$，$m\leq 100000$。
对于 $100\%$ 的数据，有 $n\leq 150000$，$m\leq 150000$。
保证所有数据合法，且 $1\leq \mathrm{value}_i \leq 1000$。