【传送门：BZOJ3376】
简要题意：
约翰和贝茜在玩一个方块游戏．编号为1到n的n(1≤n≤30000)个方块正放在地上．每个构成一个立方柱． 游戏开始后，约翰会给贝茜发出P(1≤P≤100000)个指令．指令有两种：
1．移动(M)：将包含X的立方柱移动到包含Y的立方柱上．
2．统计(C):统计名含X的立方柱中，在X下方的方块数目． 写个程序帮贝茜完成游戏．
输入格式：
• 第一行：一个整数Q， 1 ≤ Q ≤ 100000
• 第二行到Q + 1 行：每行描述一个事件，表示约翰的一个移动操作，或贝西的一个查询，首先 有一个大写字母：
– 如果字母是M，随后会有两个整数X 和Y ，约翰把积木X 移动到Y 的上方，1 ≤ X; Y ≤ N，保证移动之前X 和Y 不会在同一堆积木里；
– 如果字母是C，随后有一个整数T，表示贝西想知道在积木T 的下方还有多少其它积木， 1 ≤ T ≤ N
输出格式：
• 对每个来自贝西的查询，输出正确答案，用换行符分隔
样例输入：
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
样例输出：
1
0
3
样例解释：
第一次查询时，1 下只有一个6；第二次查询 时，3 下没有任何积木；第三次查询时，4 下有两块积木：1 和6
题解：
一开始想的时候，想到积木搭在积木上面，就想用差分来做，结果想着想着，发现，我去，带权并查集（我还是太弱了）
做法就是在并查集中维护每个集合的最上面的点、最小面的点、还有每个点与它的集合中最上面的点的距离
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; int fa[31000],v[31000]; int d[31000]; int findfa(int x) { if(x!=fa[x]) { int y=fa[x]; fa[x]=findfa(y); v[x]+=v[y]; d[x]=d[y]; } return fa[x]; } int main() { int n; scanf("%d",&n); char st[2]; memset(v,0,sizeof(v)); for(int i=1;i<=30000;i++) fa[i]=d[i]=i; for(int i=1;i<=n;i++) { scanf("%s",st+1); if(st[1]=='M') { int x,y; scanf("%d%d",&x,&y); int fx=findfa(x),fy=findfa(y); fa[fy]=fx; v[fy]=v[d[x]]+1; d[fx]=d[fy]; findfa(d[x]);findfa(d[y]); } else { int x; scanf("%d",&x); int fx=findfa(x); printf("%d ",v[d[x]]-v[x]); } } return 0; }