A22720.哈希冲突

提高+/省选-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

众所周知,模数的 hash 会产生冲突。例如,如果模的数 p=7p=7,那么 441111 便冲突了。B 君对 hash 冲突很感兴趣。他会给出一个正整数序列 value\text{value}

自然,B 君会把这些数据存进 hash 池。第 valuek\text{value}_k 会被存进 (kmodp)(k \bmod p) 这个池。这样就能造成很多冲突。

B 君会给定许多个 ppxx,询问在模 pp 时,xx 这个池内 数的总和

另外,B 君会随时更改 valuek\text{value}_k。每次更改立即生效。

保证 1p<n{1\leq p<n}

输入格式

第一行,两个正整数 nn, mm,其中 nn 代表序列长度,mm 代表 B 君的操作次数。

第一行,nn 个正整数,代表初始序列。

接下来 mm 行,首先是一个字符 cmd\text{cmd},然后是两个整数 x,yx,y

  • cmd=A\text{cmd}=\text{A},则询问在模 xx 时,yy 池内 数的总和

  • cmd=C\text{cmd}=\text{C},则将 valuex\text{value}_x 修改为 yy

输出格式

对于每个询问输出一个正整数,进行回答。

输入输出样例

  • 输入#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

说明/提示

样例解释

A 2 1 的答案是 1+3+5+7+9=25

A 3 1 的答案是 20+4+7+10=41

A 5 0 的答案是 1+10=11

数据规模

对于 10%10\%的数据,有 n1000n\leq 1000m1000m\leq 1000

对于 60%60\% 的数据,有 n100000n\leq 100000m100000m\leq 100000

对于 100%100\% 的数据,有 n150000n\leq 150000m150000m\leq 150000

保证所有数据合法,且 1valuei10001\leq \mathrm{value}_i \leq 1000

首页