(luogu3396)哈希冲突

发表于 | 分类于 ， ，

原题链接

思路:

tag上虽然打了分块但是与分块的关系只是正解的时间复杂度都是$O(\sqrt{n})$ (.

采用空间换时间的思路, 将一部分的询问直接储存下来.

  • 对于$x \in [1,\sqrt{n})$的所有询问, 直接用二维数组储存询问, 空间复杂度为$O(\sqrt{n}^2) = O(n)$, 预处理的时间复杂度为$O(n\sqrt{n})$, 更改的时间复杂度为$O(\sqrt{n})$

  • 对于$x \in [\sqrt{n},n]$的询问, 只有小于等于$\sqrt{n}$个数对答案有贡献, 因此可以直接暴力处理, 时间复杂度为$O(\sqrt{n})$.

空间复杂度为$O(n)$, 最坏情况下的时间复杂度为$O((m+n)\sqrt{n})$.

(事实上分界点也可以不选在$\sqrt{n}$处, 只要保证时间和空间不超范围就行).

代码:

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
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
const int Mn(150050),Mb(405);

int a[Mn];          //原数组
int sum[Mb][Mb];    //答案统计数组

int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    int bl = ceil(sqrt(n)); //"块"长
    for(int i(1);i<=n;++i) {
        cin >> a[i];
        for(int j(1);j<bl;++j) {    //预处理
            sum[j][i%j] += a[i];
        }
    }
    while(m--) {
        char o;
        int x,y;
        cin >> o >> x >> y;
        if(o=='A') {
            int ret(0);
            if(x>=bl) { //x大于等于块长暴力处理
                for(int i(y);i<=n;i+=x) {
                    ret += a[i];
                }
            } else {    //否则直接输出
                ret = sum[x][y];
            }
            cout << ret << endl;
        } else {
            for(int i(1);i<bl;++i) {    //更新答案统计信息
                sum[i][x%i] += y-a[x];
            }
            a[x] = y;
        }
    }
    return 0;
}