【离线+抽象并查集】代码源每日一题div1 数字替换

向右看齐 2024-03-16 16:46 16阅读 0赞

[数字替换 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![100a5eca15d24f19b42ad218a900cb26.png][]

思路：

注意到，如果直接模拟，复杂度高的原因是，操作2会重新遍历所有数，然后修改，从而变成n^2

所以，离线是为了避免这种情况

如何避免？如果倒着做，那就变成了，先把数字替换，再去插到左边，然后倒序输出就可以了

这样，我们就解决了复杂度问题

那么，如何替换数字呢，用并查集维护

**感觉这种抽象并查集就是给数字染色，同一种颜色的合并到同一个集合**

**感觉离线算法就是，把询问按一定顺序排序，变成一个好维护的过程，然后用DS维护答案，从而降低复杂度**

Code：

#include <bits/stdc++.h>
    
    #define low(x) (x&(-x))
    #define int long long
    
    using namespace std;
    
    const int mxn=5e5+10;
    const int mxe=5e5+10;
    
    struct ty{
        int op,x,y;
    };
    
    vector<ty> V;
    vector<int> ans;
    
    int N;
    int op,x,y;
    int F[mxn];
    
    void solve(){
        cin>>N;
        for(int i=1;i<=N;i++){
            cin>>op;
            if(op==1){
                cin>>x;
                V.push_back({1,x,0});
            }else{
                cin>>x>>y;
                V.push_back({2,x,y});
            }
        }
        reverse(V.begin(),V.end());
        for(int i=1;i<=N;i++) F[i]=i;
        for(int i=0;i<V.size();i++){
            if(V[i].op==1) ans.push_back(F[V[i].x]);
            else F[V[i].x]=F[V[i].y];
        }
        reverse(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++) cout<<ans[i]<<" \n"[i==ans.size()-1];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/course/10/problem/731
[100a5eca15d24f19b42ad218a900cb26.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/dc736d8ca3c846849626a1fdc743b6e4.png