分块根号

待我称王封你为后i 2024-04-17 17:54 26阅读 0赞

### 题目背景 ###

此题约为NOIP提高组Day2T2难度。

### 题目描述 ###

众所周知，模数的hash会产生冲突。例如，如果模的数`p=7`，那么`4`和`11`便冲突了。

B君对hash冲突很感兴趣。他会给出一个正整数序列`value[]`。

自然，B君会把这些数据存进hash池。第`value[k]`会被存进`(k%p)`这个池。这样就能造成很多冲突。

B君会给定许多个`p`和`x`，询问在模`p`时，`x`这个池内\*\*`数的总和`\*\*。

另外，B君会随时更改`value[k]`。每次更改立即生效。

**保证1<=p<n1<=p<n.**

### 输入格式 ###

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

第一行，`n`个正整数，代表初始序列。

接下来`m`行，首先是一个字符`cmd`，然后是两个整数`x,y`。

*  若`cmd='A'`，则询问在模`x`时，`y`池内**数的总和**。
 *  若`cmd='C'`，则将`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

const int MAXN = 151111;
    const int MAXB = 111;
    
    int num[MAXN];
    int block[MAXN][MAXB];
    
    int main(){
        Main_Init();
        int n = read(), m = read(), block_cnt = pow(n, 0.33);
        for(int i = 1; i <= n; i++){
            num[i] = read();
            for(int j = 1; j <= block_cnt; j++){
                block[j][i % j] += num[i];
            }
        }
        while(m --){
            char cons;
            while((cons = *LKF::pc ++) < 65);
            int x = read(), y = read();
            if(cons == 'A'){
                if(x < block_cnt) write('\n', block[x][y % x]);
                else {
                    int ans = 0;
                    for(int i = y; i <= n; i += x) ans += num[i];
                    write('\n', ans);
                }
            } else {
                for(int i = 1; i <= block_cnt; i++){
                    block[i][x % i] += y - num[x];
                }
                num[x] = y;
            }
        }
        Main_Init();
        return 0;
    }