题意
有一个划分成n列的星际战场，各列编号为1，2.....n。有n艘战舰，也依次编号1，2.....n,其中第i号战舰位于第i列。
有m条指令，每条指令格式如下
-
M i j 表示让第i号战舰所在列的全部战舰保持原有顺序，接在第j艘战舰的尾部。
-
C i j 表示询问第i艘战舰和第j艘战舰当前是否再同一列中，如果再同一列中，它们之间隔了多少艘战舰。
N<=30000,M<=5* (10^5)
一道简单的并查集，一条链也是一棵树，只不过是树的特殊形态，因此可以把每一列战舰看作一个集合用并查集维护。最初，N个战舰构成N个独立的集合。
在没有路径压缩的情况下fa[x]就代表排在x前面那艘战舰的编号，一个集合的代表就是位于前面的战舰，另外让树上每条边带权值1，这样树上两点之间的距离-1就是二者之间间隔的战舰数量
在考虑路径压缩的情况下,我们额外建立一个数组d，d[x]记录战舰x与fa[x]之间的边的权值。在路径压缩把x直接指向树根的同时，我们把d[x]更新为从x到树根的路径上的所有边权之和，下面的代码对Get函数稍价修改，即可实现对d数组的维护。
int get(int x){
if(x==fa[x]) return x;
int root=get(fa[x]); //递归计算集合代表
d[x]+=d[fa[x]];//维护数组d
return fa[x]=root;//路径压缩
}
当收到 C x y 指令时分别执行 get(x)和get(y)完成查询和路径压缩，当二者的返回值相同时，则说明x，y在同一列。因为x和y此时都已经指向树根，所以d[x]保存了位于x之前的战舰数量，d[y]保存了位于y之前的战舰数量，两者之差的绝对值再减去1就是x，y之间相隔的战舰数量。
当收到 M x y 指令时把x的树根作为y的树根的子节点，连接的新边的权值应该设为合并之前集合y的大小（由题意，集合y中的所有战舰都在集合x之前），因此我们还需要一个size数组在每个树根上记录集合大小。
void merge(int x,int y){
x=get(x);y=get(y);
fa[x]=y;d[x]=size[y];
size[y]+=size[x];
}
代码
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int maxn=30010;
int T,fa[maxn],d[maxn],size[maxn];
int get(int x){
if(x==fa[x]) return x;
int root=get(fa[x]);
d[x]+=d[fa[x]];
return fa[x]=root;
}
int main(){
for(int i=1;i<=maxn;++i){
fa[i]=i;
size[i]=1;
}
scanf("%d",&T);
while(T--){
char k[2];
int u,v;
scanf("%s",k);
scanf("%d%d",&u,&v);
int fa1=get(u);
int fa2=get(v);
if(k[0]== 'M'){
fa[fa1]=fa2;
d[fa1]=size[fa2];
size[fa2]+=size[fa1];
}
else{
if(fa1!=fa2) printf("-1
");
else printf("%d
",abs(d[u]-d[v])-1);
}
}
return 0;
}