有一个划分为N列的星际战场，各列依次编号为1,2,…,N。
有N艘战舰，也依次编号为1,2,…,N,其中第i号战舰处于第i列。
有T条指令，每条指令格式为以下两种之一：
1、M i j，表示让第i号战舰所在列的全部战舰保持原有顺序，接在第j号战舰所在列的尾部。
2、C i j，表示询问第i号战舰与第j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。
现在需要你编写一个程序，处理一系列的指令。
输入格式
第一行包含整数T，表示共有T条指令。
接下来T行，每行一个指令，指令有两种形式：M i j或C i j。
其中M和C为大写字母表示指令类型，i和j为整数，表示指令涉及的战舰编号。
输出格式
你的程序应当依次对输入的每一条指令进行分析和处理：
如果是M i j形式，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是C i j形式，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目，如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。
数据范围
N≤30000,T≤500000N≤30000,T≤500000
输入样例：
4
M 2 3
C 1 2
M 2 4
C 4 2
输出样例：
-1
1算法：带权并查集
带权并查集：普通的并查集是用一个f数组来记录前一个节点的位置，而带权并查集还需要用一个d数组来记录前面所以节点的总权值。
#include <iostream>
#include <cstdio>
#include <cmath> using namespace std; const int maxn = 5e5+; int f[maxn];
int d[maxn];
int size[maxn]; int find(int x) {
if(x == f[x]) {
return f[x];
}
int root = find(f[x]);
d[x] += d[f[x]]; //更新当前节点x前面的战舰数量
return f[x] = root;
} int main() {
for(int i = ; i <= maxn; i++) {
f[i] = i;
size[i] = ;
}
int n;
scanf("%d", &n);
while(n--) {
char op[];
int x, y;
scanf("%s%d%d", op, &x, &y);
int fx = find(x);
int fy = find(y);
if(op[] == 'M') {
if(fx != fy) {
f[fx] = fy; //将节点x接在节点y后面
d[fx] = size[fy]; //更新节点x前面的战舰数量
size[fy] += size[fx]; //更新此列以节点y为头节点的战舰总数量
}
} else {
if(fx == fy) {
printf("%d\n", (int)abs(d[x] - d[y]) - );
} else {
printf("-1\n");
}
}
}
return ;
}