【bzoj3376-方块游戏】带权并查集

题意：

n块积木，m个操作或询问。每次移动积木的时候，约翰会选择两块积木X，Y，把X搬到Y的上方。如果X已经和其它积木叠在一起了，那么应将这叠积木整体移动到Y的上方；如果Y已经和其它积木叠在一起了的，假设在Y上方最高处的积木为Z，那么应将X所在的那叠积木移动到Z的上方。
每次询问当前时刻，某一块积木的下方有多少块积木。
n,m<=10^5

题解：

带权并查集。
对于每个点x，维护当前所在并查集（也就是这一堆积木中）最下方的积木d[x]，最上方的积木fa[x]，x到最上方积木的距离f[x]，则下方的积木数=f[d[x]]-f[x]。
带权并查集其实就是在findfa的时候顺便维护一些权值。

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 #include<set>

 using namespace std;

 const int N=;

 int n,m,fa[N],f[N],d[N];

 char s[];

 int findfa(int x)

 {

     if(fa[x]!=x)

     {

         int y=fa[x];

         fa[x]=findfa(y);

         f[x]=f[x]+f[y];

         d[x]=d[y];

     }

     return fa[x];

 }

 int main()

 {

     // freopen("a.in","r",stdin);

     freopen("cubes.in","r",stdin);

     freopen("cubes.out","w",stdout);

     scanf("%d",&m);n=m;

     int x,y;

     for(int i=;i<=n;i++) {fa[i]=i;d[i]=i;f[i]=;}

     for(int i=;i<=m;i++)

     {

         scanf("%s",s);

         if(s[]=='M')

         {

             scanf("%d%d",&x,&y);

             int xx=findfa(x),yy=findfa(y);

             fa[yy]=xx;

             f[yy]=f[d[x]]+;

             d[xx]=d[yy];

             findfa(d[x]);findfa(d[y]);

         }

         else

         {

             scanf("%d",&x);

             findfa(x);

             printf("%d\n",f[d[x]]-f[x]);

         }

     }

     return ;

 }

巴特西

【bzoj3376-方块游戏】带权并查集

最新文章

热门文章