Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

P3396 哈希冲突

Posted on

算是一个根号分治的模板题。

Solution

可以发现暴力的复杂度等于$\sum\frac{n}{p}$，显然最坏$O(n^2)$。

考虑我们在什么时候复杂度会退化，显然是在$p$特别小的时候，所以我们考虑在$p$特别小的时候预处理，$p$特别大的时候暴力，设预处理的范围为$len$，修改的复杂度为$len$，预处理的复杂度为$nlen$，其他单次复杂度为$\frac{n}{len}$，取平衡$len=\sqrt n$，所以复杂度$O(n\sqrt n)$。

Time to Raid Cowavans

算是双倍经验。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0;
    bool flag = 0;
    char c = getchar();
    while (c < '0' || '9' < c)
    {
        if (c == '-')
            flag = 1;
        c = getchar();
    }
    while ('0' <= c && c <= '9')
        res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if (flag)
        res = -res;
}
template <class T, class... ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
template <class T>
void write(T res)
{
    if (res < 0)
        putchar('-'), res = -res;
    if (res > 9)
        write(res / 10);
    putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(const char *s)
{
    while (*s)
        putchar(*s++);
}
template <class T, class... ARC>
inline void write(T res, ARC... com) { write(res), write(com...); }
const int N = 1.5e5 + 5;
int n, m;
int a[N];
int sum[400][400];
int len;
inline void modify()
{
    int x, y;
    read(x, y);
    for(int i = 1;i <= len;i ++) sum[i][x % i] += y - a[x];
    a[x] = y;
}
int ans = 0;
inline void query()
{
    int x, y;
    read(y, x);
    if(y <= len) write(sum[y][x % y], '\n');
    else {
        ans = 0;
        x %= y;
        for(int i = x;i <= n;i += y) ans += a[i];
        write(ans, '\n');
    }
}
int main()
{
    read(n, m);
    for (int i = 1; i <= n; i++)
        read(a[i]);
    len = sqrt(n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= len; j++)
            sum[j][i % j] += a[i];
    char op[2];
    while (m--)
    {
        scanf("%s", op);
        if (op[0] == 'A') query();
        else modify();
    }
    return 0;
}