题目地址：洛谷：【P3396】哈希冲突 – 洛谷

题目描述

众所周知，模数的hash会产生冲突。例如，如果模的数p=7，那么4和11便冲突了。
B君对hash冲突很感兴趣。他会给出一个正整数序列value[]。
自然，B君会把这些数据存进hash池。第value[k]会被存进(k%p)这个池。这样就能造成很多冲突。
B君会给定许多个p和x，询问在模p时，x这个池内数的总和。
另外，B君会随时更改value[k]。每次更改立即生效。
保证 1<=p<n .

题意简述

给你一个数列，有两种操作

1. A x y，查询下标模x为y的数之和
2. C x y，修改value[x]为y

输入输出格式

输入格式：
第一行，两个正整数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

说明

样例解释
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<=1000,m<=1000.
对于60%的数据，有n<=100000.m<=100000.
对于100%的数据，有n<=150000,m<=150000.
保证所有数据合法，且1<=value[i]<=1000.

题解

参考资料：题解 P3396 【哈希冲突】 – blue’s blog – 洛谷博客
暴力地计算，修改O(1)，但查询最差可以是O(n)的。如果直接预处理答案，空间又会成O(n^2)的。
我们考虑一个问题，当模数x很小的时候，池子少但是每个池子里的数很多，而x很大的时候，池子多但每个池子里的数很少。也就是说，如果x很大，查询加进去的数其实会变小，暴力变得可以接受了，那么不如直接预处理x小的时候的结果。
我们考虑枚举模数和余数来预处理\sqrt{n}以内的模数，超过\sqrt{n}就暴力处理。预处理本身的复杂度降为了O(n \sqrt{n})的，单次查询的最坏复杂度也变成O(\sqrt{n})，总复杂度为O(n \sqrt{n})，可以接受了。
类似的优化思想同样应用在其他题目中，如[APIO2015]雅加达的摩天楼。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cmath>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'A' || c == 'C';
}

inline char readop() {
    char c;
    while(!isop(c = fgc())) {}
    return c;
}

const int MAXN = 150005;

int n, m, sqn, val[MAXN], ans[400][400];

inline int query(int p, int r) {
    if(p <= sqn) return ans[p][r];
    int res = 0;
    for(int i = r; i <= n; i += p) {
        res += val[i];
    }
    return res;
}

inline void modify(int pos, int v) {
    for(int p = 1; p <= sqn; p++) {
        ans[p][pos % p] -= val[pos];
        ans[p][pos % p] += v;
    }
    val[pos] = v;
}

char c;
int x, y;

int main() {
    n = readint(); m = readint(); sqn = sqrt(n);
    for(int i = 1; i <= n; i++) {
        val[i] = readint();
    }
    for(int i = 1; i <= n; i++) {
        for(int p = 1; p <= sqn; p++) {
            ans[p][i % p] += val[i];
        }
    }
    while(m--) {
        c = readop(); x = readint(); y = readint();
        if(c == 'A') printf("%d\n", query(x, y));
        if(c == 'C') modify(x, y);
    }
    return 0;
}