首先分析题目，数据范围特别大，500000组询问直接模拟肯定会超时，这里其实很容易可以想到用并查集。我们定义三个数组：fa[]表示每一个飞船的队首，front[]表示每一搜飞船到队首的距离，num[]表示以该飞船为队首的队伍中飞船的数量。每次M操作时就将x的队首的num值清空，并将fa值改变为y的队首，再将front值更新即可。询问时只要判断fa是否相等就可以了，不相等的话直接输出-1,否则输出abs(front[x]-front[y])-1。
Code：
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<iomanip> #include<iostream> #include<algorithm> using namespace std; const int N=3e4+7; int n,fa[N],dis[N],cnt[N]; inline int read() { char ch=getchar();int num=0;bool flag=false; while(ch<'0'||ch>'9'){if(ch=='-')flag=true;ch=getchar();} while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();} return flag?-num:num; } inline int Abs(int x) {return x>0?x:-x;} inline int find(int x) { if(fa[x]==x)return x; int fx=find(fa[x]); dis[x]+=dis[fa[x]]; return fa[x]=fx; } int main() { n=read(); char s;int x,y; for(int i=1;i<=30000;i++) fa[i]=i,dis[i]=0,cnt[i]=1; for(int i=1;i<=n;i++){ cin>>s; x=read();y=read(); int fx=find(x),fy=find(y); if(s=='M'){ if(fx==fy)continue; dis[fx]+=cnt[fy]; fa[fx]=fy; cnt[fy]+=cnt[fx]; cnt[fx]=0;} else{ if(fx!=fy)printf("-1 "); else printf("%d ",Abs(dis[x]-dis[y])-1); } } return 0; }