ABC329F Colored Ball

Tag：启发式合并

题目描述

给定 \(N\) 个盒子，每个盒子里面有一个颜色为 \(C_i\) 的小球。有 \(Q\) 次操作，每次操作将第 \(a_i\) 个盒子中的球都放到第 \(b_i\) 个盒子里面，你需要在每次操作后输出当前操作结束后第 \(b_i\) 个盒子里面有多少个不同颜色的小球。

如果盒子为空，输出 \(0\) 即可。

数据说明：

\(1 \leq N, Q \leq 200000\)
\(1 \leq C_i \leq N\)
\(1 \leq a, b \leq N\)
\(a \neq b\)

分析

按照题目来说很好想到用 \(\text{set}\) 来维护集合。

由于需要合并集合，可以想到启发式合并，每次合并两个集合的时候我们遍历小的集合，把其中所有的元素都插入到较大的集合当中。因为题目要我们输出的是 \(b_i\) 集合的球种类，我们固定把小的合并到大的中，可以通过 \(\text{swap}\) 来解决固定是合并到 \(b_i\) 这个问题。这个 \(\text{STL}\) 的 \(\text{swap}\) 是 \(O(1)\) 的。

上述做法中操作的次数为 \(O(nlogn)\)，单次 \(\text{set}\) 的插入复杂度为 \(O(logn)\)，因此上述做法的综复杂度为 \(O(nlog^2{n})\)

代码实现

void NeverSayNever() {
    int n,q; cin >> n >> q;
    vector<set<int>> vec(n);
    for(auto &x : vec){
        int tmp; cin >> tmp;
        x.insert(tmp);
    }
    while(q--){
        int a,b; cin >> a >> b;
        a--,b--;
        if(vec[a].size() < vec[b].size()){
            for(auto &x : vec[a]){
                vec[b].insert(x);
            }
            vec[a].clear();
        }else{
            for(auto &x : vec[b]){
                vec[a].insert(x);
            }
            vec[b].clear();
            swap(vec[a],vec[b]);
        }
        cout << vec[b].size() << endl;
    }
}

日志

本页面创建于 2024/09/13 10:41