(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
44
#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;
}