题目背景

\(Cube Stacking, 2004 Open\)

题目描述

约翰和贝西在叠积木。共有\(30000\)块积木，编号为\(1\)到\(30000\)。一开始，这些积木放在地上，自然地分成\(N\)堆。贝西接受约翰的指示，把一些积木叠在另一些积木的上面。一旦两块积木相叠， 彼此就再也不会分开了，所以最后叠在一起的积木会越来越高。约翰让贝西依次执行\(P\)条操作，操作分为两种：

 第一种是移动操作，格式为“移动\(X\)到\(Y\)的上面”。\(X\)和\(Y\)代表两块积木的编号，意思是将X所的那堆积木，整体叠放到\(Y\)所在的那堆积木之上；

 第二种是统计操作，格式为“统计\(Z\)下方的积木数量”。\(Z\)代表一块积木的编号，意思是贝西需要报告在编号为\(Z\)的积木之下还有多少块积木

请编写一个程序，帮助贝西回答每条统计问题。

输入输出格式

输入格式：

 第一行：单个整数：\(P，1 ≤ P ≤ 10^5\)

 第二行到第\(P + 1\)行：每行描述一条命令，如果这行开头的字母是 \(M\)，代表一条移动命令，后面的两个整数代表上文中的X和\(Y\)；如果开头字母是 \(C\)，代表一条统计命令。后面的整数代表上文中的\(Z\)，保证所有的移动命令都有意义，\(X\)和\(Y\)不会已经出现在同一堆积木里

输出格式：

 对每一个统计命令，输出正确回答，用换行符分开每个查询的结果

输入输出样例

输入样例#1：

6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4

输出样例#1：

1
0
2

说明

第一次查询时， \(1\) 下面只有一个 \(6\)；第二次查询时， \(3\) 下面没有任何积木；第三次查询时，\(4\) 下面有两块积木：\(1\) 和 \(6\)

思路：并查集的题目就是不一样，代码短小精悍，思路却很难想……对于这道题目来说，我们用一个\(s\)数组表示某个积木上方有多少个积木，再用一个数组\(a\)表示以某个点为顶的积木的个数，在并查集路径压缩的过程中让\(s[x]+=s[fa[x]]\)，就是说\(x\)的父亲是在\(x\)上面的，那么就把它父亲上面的积木也加到\(x\)上面来，然后对于每个移动命令，是把以\(x\)为顶的那一块放到\(y\)上面，那么我们就更新\(x\)是\(y\)的父亲，然后以\(x\)为顶的积木个数变成了原本以\(x\)为顶的积木个数加上原本以\(y\)为顶的积木个数，\(y\)上方的积木个数就加上了原本以\(x\)为顶的积木个数，然后对于每个统计命令，因为要求对于\(x\)输出\(x\)下面的积木的个数，那么就是以\(x\)为顶的积木个数减去\(x\)上面的积木个数再减\(1\)(因为\(x\)不在\(x\)的下方)。

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#define maxn 30007
using namespace std;
int p,fa[maxn],s[maxn],a[maxn];
string s1;
inline int qread() {
  char c=getchar();int num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';
  return num*f;
}
int find(int x) {
  if(fa[x]==x) return x;
  int res=find(fa[x]);
  s[x]+=s[fa[x]];
  return fa[x]=res;
}
int main() {
  p=qread();
  for(int i=1;i<=30000;++i) a[i]=1,fa[i]=i;
  for(int i=1,x,y;i<=p;++i) {
    cin>>s1;
    if(s1=="M") {
      x=qread(),y=qread();
      int zrj=find(x),cyh=find(y);
      if(zrj!=cyh) {
        fa[cyh]=zrj;
        s[cyh]+=a[zrj];
        a[zrj]+=a[cyh];
        a[cyh]=0;
      }
    }
    else {
      x=qread();
      int zrj=find(x);
      printf("%d\n",a[zrj]-s[x]-1);
    }
  }
  return 0;
}