题解

题目描述： Farmer John 和 Betsy 正在玩一个游戏，游戏中有 N（1 ≤ N ≤ 30,000）个相同的立方体，编号从 1 到 N。游戏开始时，有 N 堆立方体，每堆只有一个立方体。Farmer John 要求 Betsy 执行 P（1 ≤ P ≤ 100,000）次操作。操作分为两种类型：移动操作和计数操作。

• 移动操作：将包含立方体 X 的堆移动到包含立方体 Y 的堆的顶部。
• 计数操作：统计在包含立方体 X 的堆中，位于立方体 X 下方的立方体数量，并报告该值。

输入格式：

• 第 1 行：一个整数 P，表示操作的数量。
• 第 2 到 P+1 行：每行描述一个合法的操作。每行以 'M' 开头表示移动操作，或以 'C' 开头表示计数操作。对于移动操作，该行还包含两个整数 X 和 Y。对于计数操作，该行还包含一个整数 X。

输出格式： 按输入文件的顺序输出每个计数操作的结果。

解题思路

数据结构选择：

• 并查集（Disjoint Set Union, DSU）：用于高效管理立方体的堆合并和查找操作。
• 父节点数组 fa：fa[x] 表示节点 x 的父节点。
• 深度数组 h：h[x] 表示节点 x 下方的立方体数量。
• 堆大小数组 s：s[x] 表示以 x 为根的堆的大小。

操作处理：

1. 移动操作（M X Y）：

   • 找到 X 和 Y 的根节点 rootX 和 rootY。
   • 如果 rootX == rootY，则无需操作。
   • 否则，将 rootX 的父节点设为 rootY，并更新 h[rootX] 为 s[rootY]（因为 X 堆移动到 Y 堆后，X 堆的所有立方体都在 Y 堆的顶部，X 的深度为 Y 堆的大小）。
   • 更新 s[rootY] 为 s[rootX] + s[rootY]（合并后的堆大小）。

2. 计数操作（C X）：

   • 找到 X 的根节点，并更新 h[X] 的值（通过路径压缩）。
   • 输出 h[X]，即 X 在其堆中的深度。

代码实现

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=30005;
int n=30000,p,fa[maxn],s[maxn],h[maxn];
//fa[i]表示i的父节点（并查集）
//s[i]表示第i个箱子所在的箱子堆的箱子总数
//h[i]表示第i个箱子下面的箱子个数
int read(){int x;scanf("%d",&x);return x;}
bool pd()//判断这个这次操作是M还是C
{
	char ch=getchar();
	while (ch!='M'&&ch!='C') ch=getchar();
	return ch=='M';
}
int get(int x)//并查集合并操作
{
	if (fa[x]==x) return x;
	int f=get(fa[x]);
	h[x]+=h[fa[x]];
	//把父节点下面的点加上，如果已经全部累计上了，不用担心会重复，因为祖先节点下面没有其它箱子
	return fa[x]=f;
}
int main()
{
	p=read();
	for (int i=1;i<=n;i++) fa[i]=i,h[i]=0,s[i]=1;
	for (int i=1;i<=p;i++)
	{
		if (pd())
		{
			int x=get(read()),y=get(read());
			if (x==y) continue;
			fa[x]=y;h[x]+=s[y];s[y]+=s[x];
		}else
		{
			int x=read();get(x);
			printf("%d\n",h[x]);
		}
	}
	return 0;
}