DDOSvoid's Blog

2020 China Collegiate Programming Contest Changchun Onsite K. Ragdoll

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/gym/102832/problem/K

Solution

对于 $(x,y)=x\oplus y$，我们考虑对于每个 $x$ 合法的 $y$ 有多少个

注意到数量一定是小于 $\sigma(x)$ 的，通过枚举 $x$ 的约数打表能够发现最多不会超过 $c=60$

我们考虑提前预处理好 $x$ 的合法点 $y$，复杂度是 $O(n\log^2 n)$

然后对于题目中的合并操作，我们直接用 $unordered\underline{}map$ 启发式合并即可

时间复杂度为 $O(cn\log n)$，$unordered\underline{}map$ 查找某个权值的复杂度为 $O(1)$ 

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
#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <vector>
#define maxn 300010
#define ll long long 
using namespace std;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } 

int n, m;

int v[maxn];

vector<int> a[maxn];
void init(int n) {
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i) {
            int k = i ^ j;
            if (gcd(k, j) == i) a[j].push_back(k); 
        }
}

int fa[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

unordered_map<int, int> mp[maxn];

ll ans;
inline void solve_1() {
    int x, y; cin >> x >> y;
    v[x] = y; mp[x][v[x]] = 1; 
}

inline void solve_2() {
    int x, y, fx, fy; cin >> x >> y;
    if ((fx = find(x)) == (fy = find(y))) return;
    if (mp[fx].size() < mp[fy].size()) swap(fx, fy);
    for (auto u : mp[fy]) 
        for (auto v : a[u.first])
            if (mp[fx].find(v) != mp[fx].end())
                ans += (ll) mp[fx][v] * u.second;
    for (auto u : mp[fy]) mp[fx][u.first] += u.second;
    fa[fy] = fx;
}

inline void solve_3() {
    int x, y, fx; cin >> x >> y;
    fx = find(x);
    for (auto u : a[v[x]])
        if (mp[fx].find(u) != mp[fx].end())
            ans -= mp[fx][u];
    --mp[fx][v[x]]; v[x] = y; ++mp[fx][v[x]]; 
    for (auto u : a[v[x]])
        if (mp[fx].find(u) != mp[fx].end())
            ans += mp[fx][u]; 
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; init(200000); init_fa(n + m); 
    for (int i = 1; i <= n; ++i) cin >> v[i], mp[i][v[i]] = 1; 
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        switch (opt) {
        case 1 : solve_1(); break;
        case 2 : solve_2(); break;
        case 3 : solve_3(); break;       
        }
        cout << ans << "\n";
    }
    return 0; 
}