银河英雄传说TJ

题目背景

公元5801年，地球居民迁至金牛座第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。

宇宙历799年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特(B)率领十万余艘战舰出征，气吞山河集团点名将杨威利(A)组织麾下三万艘战舰迎敌。~~（废话）~~

题目描述

概括

两个阵营打仗，A方有30000艘战舰，开始每艘战舰独自占一行，A有时会给出合并指令，格式为M i j ，每次都将处在i号战舰所在行整体移到j号战舰所在行的最后。
有时B会发出查询指令，格式为C i j，如果i和j在同一列(pre[i]==pre[j])那么输出i和j的距离；如果不在同一列，就输出-1。

输入输出格式

输入格式

第一行一个整数T，1<=t<=5*10⁵，表示一共有T条指令。
以下T行，每行一个指令。指令分为两种：

M i j : 为杨威利的指令，表示合并
C i j : 为莱因哈特的指令，表示查询

输出格式

依次对输入的指令进行分析和处理：
如果是M，不输出，把j这列的战舰直接移动到i这列的末尾~~（就是合并嘛）~~
如果是C，若i和j在同一列，输出i与j之间的战舰数目；若不在同一列，则输出-1

分析

对于这道题，首先不能被它的NOI身份和较长的描述吓到。

仔细观察，因为是并查集，所以可以把一艘战舰看成一个点，它所在的这排的第一艘船就可以看成根节点，这就具备了并查集的基本形状。

可以把问题分解成几个小问题：

如何存储前面的战舰，学过并查集的都知道用pre数组存
如何存储一个点到根节点的距离，执行C操作需要，我的想法是再开一个dis数组，直接记录每一个点到它的根节点的距离
如何实现M操作，朴素并查集的合并是直接合并根节点，不满足题目需要，所以可以用一个num数组，记录每一排的战舰数，每次合并时直接在dis[i]上加num[j]，就可以对同一排内的战舰进行顺序区分

可以看到，每次dis[i]变化时，都是加上num[j]，但pre[find(i)]可以直接连到pre[find(j)]上，这样就解决了M操作的问题
那么C操作其实就是求从i到j的节点数，因为有dis记录两点到同一点(根节点)，就可以直接转化为求dis[i]-dis[j]的绝对值
所以问题就解决了，总共需要三个数组：pre,dis,num

Code

#include<bits/stdc++.h>
using namespace std;
int t;
char f;
int a,b;
int pre[30001],dis[30001],num[30001];
int find(int x){//带权并查集的路径压缩find
	if (pre[x]==x)return x;
	int sum=find(pre[x]);
	dis[x]+=dis[pre[x]];
	return pre[x]=sum;
}
int main(){
	scanf("%d",&t);
	for (int i=1;i<=30000;++i){
		pre[i]=i;
		num[i]=1;
	}
	for (int i=1;i<=t;++i){
		cin>>f;
		scanf("%d %d",&a,&b);
		int x=find(a),y=find(b);
		if (f=='M'){
			dis[x]=num[y];//x点到了末尾
			num[y]+=num[x];//b排要加上a排原数
			num[x]=0;//a排已经并到b排，所以没有战舰
			pre[x]=y;//真正的合并
		}
		else{
			if (x!=y){
				printf("-1\n");
			}
			else{
				printf("%d\n",abs(dis[a]-dis[b])-1);
			}
		}
	}
	return 0;
}