根号分治

整理题意：给定长度为 $n$ 的序列 $a$ 和 $m$ 次操作，第 $i$ 次操作要么给定一个 $i$ 并修改 $a_i$ 的值；要么给定整数 $p,k$ 询问满足 $i \bmod p = k$ 的 $a_i$ 之和。

根号分治，对于 $p \leq \sqrt{n}$ 的询问，预处理 $s_{p,k}$ 为满足 $i \bmod p = k$ 的 $a_i$ 的和，可以 $O(1)$ 回答询问。对于 $p > \sqrt{n}$ 的询问，遍历满足要求的整数 $i$ 的时间复杂度为 $O(\sqrt{n})$。

对于修改操作，修改 $a$ 的时间复杂度为 $O(1)$，修改 $s$ 的时间复杂度为 $O(\sqrt{n})$。

由于 $n,m$ 同阶，总体时间复杂度 $O(n \sqrt{n})$。

#include<bits/stdc++.h>
using namespace std;
constexpr int B=400;
int n,m,a[150'005],s[405][405];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=B;j++) s[j][i%j]+=a[i];
    for(int i=1;i<=m;i++){
        static char c[4];
        static int x,y;
        scanf("%s%d%d",c+1,&x,&y);
        if(c[1]=='C'){
            for(int j=1;j<=B;j++) s[j][x%j]+=y-a[x];
            a[x]=y;
        }
        else{
            int ans=0;
            if(x<=B) ans=s[x][y];
            else for(int j=y;j<=n;j+=x) ans+=a[j];
            printf("%d\n",ans);
        }
    }
    return 0;
}