题目：
有一个划分为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
解题报告：边带权并查集的使用，咱们把每一列的战舰看成一个集合，用并查集维护，最初的时候，n个战舰就是n个独立的集合。
在没有进行路径压缩的时候，far[x]就表示排在第x号战舰前边的那个战舰的编号，一个集合的代表就是位于最前边的战舰，另外，让树上的每条边带权值1，这样树上两点之间的距离减一就是两点之间间隔的战舰数目。
在考虑路径压缩的情况下，咱们需要单独开设一个数组d，d[x]记录战舰x与far[x]之间的边的权值。在路径压缩把x连接到根节点的同时，把d[x]更新为从x到根节点的路径上的所有边权之和。
下边的find函数增加了部分语句，实现了对d数组的维护：1 int find(int x) 2 { 3 if(far[x]==x) 4 { 5 return x; 6 } 7 int root=find(far[x]); 8 data[x]+=data[far[x]]; 9 return far[x]=root; 10 }
当接受到一个C x y 指令时，分别执行find(x) ,find(y) 完成查询和路径压缩，若二者返回值相同，则说明在同一列，因为x，y这时都指向了根节点，所以d[x]存放了位于x之前的战舰数目，d[y]存放了位于y之前的战舰数目，二者之差的绝对值再减一，就是x，y之间间隔战舰的数目。
当接受到一个M x y指令时，把x的根节点作为y的根节点的子结点，连接新边的权值应该设为合并之前集合y的大小，因此我们还需要一个size数组，在每个树根上记录集合的大小。
merge函数：
1 void merge(int x,int y) 2 { 3 x=find(x); 4 y=find(y); 5 far[x]=y; 6 data[x]=size[y]; 7 size[y]+=size[x]; 8 }
ac代码：
//from:Onion
//acwing 238 银河英雄传说 边带权并查集
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=3e4+1000;
int size[maxn],far[maxn],data[maxn];
void init()
{
for(int i=0;i<maxn;i++)
{
size[i]=1;
data[i]=0;
far[i]=i;
}
}
int find(int x)
{
if(far[x]==x)
{
return x;
}
int root=find(far[x]);
data[x]+=data[far[x]];
return far[x]=root;
}
void merge(int x,int y)
{
x=find(x);
y=find(y);
far[x]=y;
data[x]=size[y];
size[y]+=size[x];
}
int main()
{
init();
int t;
scanf("%d",&t);
int x,y;
char cmd;
while(t--)
{
getchar();
scanf("%c%d%d",&cmd,&x,&y);
if(cmd=='M')
{
merge(x,y);
}
else
{
if(find(x)==find(y))
{
printf("%d
",abs(data[x]-data[y])-1);
}
else
{
printf("-1
");
}
}
}
}