题目翻译:有n个箱子，初始时每个箱子单独为一堆；接下来有p行输入，M x y 或者 C x y 对于M x y：表示将x箱子所在的一堆箱子搬到y所在的那一堆箱子上； 对于C x y表示求箱子x下面有多少个箱子； 输出：在箱子x所在的那堆中，求出在x之下的cube的个数。

大致思路:与题解59一样,又是涉及到合并(M x y)与查询(C x y)的问题,故使用并查集解决.但我们在这里还能使用路径压缩吗?在路径压缩的过程中,会不会影响中间堆放的箱子的个数?当然会,但我们只有开数组,在合并之后,马上记录(更新)某个原来的根节点没被压缩前一路上堆放的箱子数即可,还要时刻记录某一堆堆放了多少个箱子,在合并加给上面对方箱子的根节点做记录

思路&AC代码:

#include<iostream>
using namespace std;
int fa[30010],nextc[30010],dsum[30010];
int find(int x)//在找根节点,递下去,然后归的时候就更新好了路径上的(包括查找的这个点)各个原始根节点下面的箱子数,并实现了路径压缩
{
    if(fa[x]==x) {return x;}//找到最根节点,直接返回
    int tmp=fa[x];//路径压缩后的fa[x]就变了,被压缩了,他下面的箱子数是不准确的,所以提前把没压缩前,一路堆放的箱子个数保存下来
    fa[x]=find(tmp);//路径压缩
    //nextc在合并的时候就计算过了
    nextc[x]+=nextc[tmp];//在路径压缩找最根节点的同时,记录下路径上经过的cube的个数,避免路径压缩影响块的个数
    return fa[x];//路径压缩
}
void merge(int a,int b)//a->输入的x,b->输入的y,要将x放到y的堆顶
{
    a=find(a);//都是在对某个数所在的栈进行操作,所以要找到根节点
    b=find(b);//由题意,x!=y,不需要再判断
    fa[a]=b;//x管y叫父(跟)节点,方便后续(连环)路径压缩
    nextc[a]+=dsum[b];//x下面堆放了y这一堆总共的箱子个数
    dsum[b]+=dsum[a];//y这一堆的总箱子数新增了x这一堆的箱子数
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    for(int i=1;i<=30000;++i) {fa[i]=i;}//创造堆,没用到的也没关系,不影响
  //fill函数的参数左闭右开,类似于循环赋值
    fill(dsum+1, dsum+30001, 1);//memset按bit赋值,memset只能填0或-1,填1会变成一个很大的数
    int p,tx,ty;cin>>p;
    char t;
    while(p--)
    {
        cin>>t;
        if(t=='M') {cin>>tx>>ty;merge(tx,ty);}
        else {cin>>tx;find(tx);cout<<nextc[tx]<<'\n';}//find承担着更新某个箱子下面叠放的箱子数(merge只是更新了每个祖先(根节点)下面的箱子数,不find()一下不一定更新过某个箱子下面叠放的箱子数)
    }
    return 0;
}