abc183 F(启发式合并)

补题？补题！

题意：

现在有$n$个小孩，他们分别属于$C_i$班级，初始的时候他们分别属于自己的小组，现在有如下两个操作：

1、1 x y：将x和y所属的小组合并在一起

2、2 x y：输出y班级中和x一个小组的人数。

题解：

这题就是一个一眼并查集的题，我们用一个$map$的数组存一下每个小组里面班级的数量有多少个，然后$1$操作就直接合并，$2$操作输出即可。但是，$TLE$了？为啥，并查集不是$log$的操作么，没错，的确是，但是我们要知道，一个小组的人数一多，我们在合并更新的时候，是要去遍历那个小组的班级的，那么时间复杂度就被拉高了，那么我们就需要启发式合并了，即子树小的合并到子树大的里面去，这很重要，可以极大地减小时间复杂度。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define FI first
#define SE second
#define _for(type,i,a,b) for(type i = (a);i<(b);++i)
#define _sfor(p,st) for(auto &p:st)
#define endl '\n'


const int N=2e5+5;
int fa[N];
map<int,int>cs[N];
void init(int n){
  _for(int,i,1,n+1)fa[i]=i;
}
int find(int x){
  return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
  x=find(x),y=find(y);
  fa[x]=y;
  _sfor(it,cs[x]){
    cs[y][it.FI]+=it.SE;
  }
}
signed main() {
  FIO;
  int n,q;cin>>n>>q;
  init(n);
  _for(int,i,1,n+1){
    int x;cin>>x;
    cs[i][x]++;
  }
  while(q--){
    int op,x,y;cin>>op>>x>>y;
    if(op==1)merge(x,y);
    else cout<<cs[find(fa[x])][y]<<endl;
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/11/16/abc183-F-启发式合并/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！