银河英雄传说

有一个划分为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≤500000

输入样例：
4
M 2 3
C 1 2
M 2 4
C 4 2

输出样例：
-1
1

emmmmmmm，很明显的并查集，而且还是带权并查集。

那应该怎么做呢？一般来说，带权并查集都需要另外开一个数组来记录一些距离信息，这道题很明显得，就是要记录当前这个战舰到根节点战舰的距离，从而得到同一个根节点的两艘战舰的距离就是abs(sum[b]-sum[a])-1

所以我们需要做的就是不断地维护这个sum数组。对此我们需要开一个新的数组表示当前的这一列战舰的数量。

#include<bits/stdc++.h>
using namespace std;
int n,t,f[30010],sum[30010],cnt[30010];//cnt为当前这一列的长度 ,sum为当前战舰到根节点的战舰数量
int find_root(int x)
{
	if(x!=f[x])
	{
		int t=f[x];
		f[x]=find_root(f[x]);
		sum[x]+=sum[t];  //维护sum[x],加上父亲节点到根节点的距离
	}
	return f[x];
}
void union_set(int a,int b)
{
	int fa=find_root(a);
	int fb=find_root(b);
	if(fa!=fb)
	{
		f[fa]=fb;
		sum[fa]=cnt[fb];//因为是连接到最后，所以fa应该加上fb那一列战舰的数量
		cnt[fb]+=cnt[fa];//fb这一列战舰的数量加上fa这一列战舰的数量....不懂就画一下图就懂了
	}
}
int main()
{
	ios::sync_with_stdio(false);//加速cin,,,cout
	for(int i=1;i<=30000;i++)	f[i]=i,cnt[i]=1;//让自己的根节点为自己，自己这一列的战舰数量为1
	cin>>t;
	while(t--)
	{
		string op;
		int i,j;
		cin>>op>>i>>j;
		if(op=="M")	union_set(i,j);
		else
		{
			if(i==j)	cout<<0<<endl;//如果是同一个战舰就是0啦
			else	if(find_root(i)==find_root(j))	cout<<abs(sum[i]-sum[j])-1<<endl;//上面的公式，不懂画图
			else	cout<<-1<<endl;
		}
	}
	return 0;
}