题目

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int n, m;
int a[150000];
int st[400], en[400], sum[400][205][205];
int bel[150000], num, sz;
int maxp = 200;
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    num = sqrt(n), sz = n / num;
    maxp = min(maxp, sz);
    for (int i = 1; i <= num; i++) {
        st[i] = sz * (i - 1) + 1;
        en[i] = sz * i;
        if (i == num) en[i] = n;
        for (int j = st[i]; j <= en[i]; j++) {
            bel[j] = i;
            for (int p = 1; p <= maxp; p++) {
                sum[i][p][j % p] += a[j];
            }
        }
    }
    while (m--) {
        char op;
        int x, y;
        cin >> op >> x >> y;
        int ans = 0;
        if (op == 'A') {
            if (x > maxp) {
                for (int i = y; i <= n; i += x) {
                    ans += a[i];
                }
            } else {
                for (int i = 1; i <= num; i++) {
                    ans += sum[i][x][y];
                }
            }
            cout << ans << '\n';
        } else {
            int now = bel[x];
            int bef = a[x];
            a[x] = y;
            for (int p = 1; p <= maxp; p++) {
                sum[now][p][x % p] += -bef + a[x];
                
            }
        }
    }
    return 0;
}