题目链接: 

题目大意：每次指定一块砖头，移动砖头所在堆到另一堆。查询指定砖头下面有几块砖头。

解题思路：

【HDU数据有问题】，数据从0开始，且给定n块砖头（比如1000），数据会有第1005块砖头，导致访问越界。

【解决方案】，并查集初始化范围改为0~maxn(30005)

 

由于只给定一块砖头，却要移动所在堆。所以需要并查集维护所在堆。

p[x]=y，即x所在堆的堆底是y，注意此时并查集是有方向的。

用under[x]维护x下面有几块砖头，sum[x]维护x所在堆一共有几块砖头。

 

对于移动x堆到y堆，首先对x和y的堆底两点处理，合并后，X堆、Y堆所有点的堆底都指向Y堆的堆底：

①获取x和y所在堆的堆底，即X=find(x)，Y=find(y)

②under[X]=sum[Y]，即合并后，X堆下面有Y堆总个数

③sum[Y]+=sum[X]，由于合并后，两堆结点在路径压缩时会集体更新，所以这里只要令sum[Y]=两堆和就可以了。

③f[X]=Y,让X堆的堆底都指向Y堆堆底。

 

路径压缩部分:

①under[x]+=under[f[x]]，即原X堆堆底以上的under，全部加上堆底under（堆底已经被手动更新）。

②f[x]=find(f[x])，堆底以上的指向更新。

 

#include "cstdio"#define maxn 30005int f[maxn],under[maxn],sum[maxn];int find(int x){    if(x!=f[x])    {        int t=find(f[x]);        under[x]+=under[f[x]];        return f[x]=t;    }    else return x;}void Union(int x,int y){    x=find(x),y=find(y);    if(x!=y)    {        under[x]=sum[y];        sum[y]+=sum[x];        f[x]=y;    }}int main(){    //freopen("in.txt","r",stdin);    int n,x,y;    char cmd;    scanf("%d",&n);    for(int i=0;i