并查集启发式合并

秒速五厘米 2022-12-21 04:49 137阅读 0赞

并查集启发式合并

挺简单的一算法，只是我以为树上启发式合并也是这么简单的所以在这上面吃了大亏，还有一点提醒就是

map不是映射么，如果map该key对应没有值的话，你直接用下标访问的话会新建一个点，反正就是不知名原因会T,我卡一晚上这个点了，所以建议用count函数判断该key是否有值，再进行下标访问

扯远了，并查集启发式合并就是合并连通块时，吧小的连通块塞进大的里面（这就完了）

[例题][Link 1]

给你一个初值为n'颗树每个树只有一个节点，每个节点都有个权值的森林

贡献点对为 如果节点i和节点j在一颗树里面且 ai^aj==\_\_gcd(ai,aj) ans++

然后三种操作

chose x y

chose=1 建立一个新树节点为x 权值为y

chose=2 合并x节点所在点的树和y节点所在的树

chose =3 节点x的权值改为y

没什么好说的就是预处理每个值能配对的值，存起来，平均长度为10左右

然后并查集启发式合并维护就好，查的时候用hashmap就好

代码如下

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=4e5+7;
    int f[N];
    unordered_map<int,ll>son[N];
    vector<int>v[N],sum[N];
    ll ans;
    int a[N];
    int fid(int x)
    {
        if(f[x]==x)
            return f[x];
        return f[x]=fid(f[x]);
    }
    void join(int x,int y)
    {
        int fx=fid(x);
        int fy=fid(y);
        if(fx==fy) return;
        if(son[fx].size()<son[fy].size()) swap(fx,fy);
        f[fy]=fx;
        for(auto i:son[fy])
        {
            int d=i.first;
            for(int j=0;j<sum[d].size();j++)
                if(son[fx].count(sum[d][j]))
                ans+=i.second*son[fx][sum[d][j]];
        }
        for(auto i:son[fy])
            son[fx][i.first]+=i.second;
        son[fy].clear();
    }
    int main()
    {
    
        for(int i=1;i<=2e5;i++)
        {
    
            for(int j=i+i;j<=2e5;j+=i)
            {
                int k=j^i;
                if(i==__gcd(j,k))
                sum[j].push_back(k);
            }
        }
    
    
        //for(int i=1;i<=1000;i++) cout<<sum[i].size()<<endl;
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
             scanf("%d",&a[i]);
            //for(int j=0;j<sum[a[i]].size();j++) cout<<sum[a[i]][j]<<' ';cout<<endl;
            int a1=a[i];
           son[i][a1]++;
           f[i]=i;
          
        }
        while(m--)
        {
            int chose,a1,a2;
             scanf("%d%d%d",&chose,&a1,&a2);
            if(chose==1)
            {
                son[a1][a2]++;
                f[a1]=a1;
                a[a1]=a2;
               
                //for(int j=0;j<sum[a1].size();j++) cout<<sum[a1][j]<<' ';cout<<endl;
            }
            else if(chose==2)
            {
                join(a1,a2);
            }
            else
            {
                int d=fid(a1);
                for(int i=0;i<sum[a[a1]].size();i++)
                {
                    int t=sum[a[a1]][i];
                    //if(son[d].count(t))
                    ans-=son[d][t];
                }
               son[d][a[a1]]--;
               a[a1]=a2;
                for(int i=0;i<sum[a2].size();i++)
                {
                    int t=sum[a2][i];
                    ans+=son[d][t];
                }
                son[d][a2]++;
            }
           printf("%lld\n",ans);
    
        }
    }
    /*
    3 6
    3 2 1
    2 1 2
    1 5 3
    2 1 2
    2 3 2
    2 5 1
    3 3 2
    
    */

[Link 1]: https://codeforces.com/gym/102832/problem/K