P3396 哈希冲突

这个套路还是蛮常见的

思路: 将操作分为两类, 大于$\sqrt{n}$ 的, 和小于它的

为什么要这么干

考虑暴力 , 每次修改$O(1)$ , 每次查询$O(n)$

那么它的复杂度是$O(n^2)$ 的

观察发现, 修改的复杂度远小于查询, 导致复杂度不平衡

考虑在修改时预处理以降低查询复杂度

修改时处理将x膜1 ~ $\sqrt{n}$ 加上a[x], cnt[x] += a[x], $O(\sqrt{n})$

查询时, 如果x < $\sqrt{n}$ , 直接输出 mod[x][y%x] , 否则 暴力枚举 , 复杂度$O(\sqrt{n})$

总复杂度$O(\sqrt{n})$

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int siz; long long cnt[500000], mod[500][500]; int read(void) { int x = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)) { x = (x << 3) + (x << 1) + c - '0'; c = getchar(); } return x; } int n, m; int a[200005]; void add(int x,int k) { for (int i = 1;i <= siz; i++) mod[i][x % i] += k; cnt[x] += k; } int main() { n = read(), m = read(); siz = sqrt(n); for (int i = 1;i <= n; i++) { a[i] = read(); add(i, a[i]); } char s[5]; while (m--) { scanf ("%s", s); int x = read(), y = read(); if (s[0] == 'C') { add(x, -a[x]); a[x] = y; add(x, y); } else { y %= x; if (x <= siz) printf ("%lld\n", mod[x][y]); else { int val = 0; for (int i = y;i <= n; i += x) val += cnt[i]; printf ("%d\n", val); } } } return 0; }