题意
有两个名为xxx的神奇数据结构，xxx A A A 有最多 30000 30000 30000 个点，开始每行都只有一个点。
有时会给出合并指令，格式为 M M M i i i j j j，每次都将处在第 i i i个点所在行整体移到第 j j j 个点所在行的最后。
有时会给出查询指令，格式为 C C C i i i j j j，询问。
分析
对于这道题，首先不要被它的NOI身份(就是个古早的t1)和较长的描述(实际也不长)吓到。
仔细观察，因为要用并查集，所以可以把每一行的第一个点就可以看成根节点，这就具备了并查集的基本形状。
可以把问题分成几个小问题：
- 记录每个点在哪一行：
因为这是并查集的题，所以可以用并查集实现。 - 计算同一行内两个点的距离：执行 f i n d find find 操作时，因为要对 p r e pre pre 数组进行路径压缩(不然容易炸空间&时间)，所以较难直接用 p r e pre pre 求解，再开一个 d i s dis dis 数组，直接记录每一个点到它的根节点的距离，需要时直接做差求绝对值就好了。
- 实现题目中的合并操作：一般并查集的合并操作是直接合并每棵树的根节点(改变 p r e pre pre 数组)，不会改变其他如 d i s dis dis 的值，所以可以用 n u m num num 数组，记录每一排的节点数，每次合并时直接在 d i s i dis_i disi 上加 n u m j num_j numj，就可以对同一排内的点进行顺序区分。
可以看到，每次 d i s i dis_i disi 变化时，都会加上 n u m j num_j numj，但 p r e f i n d ( i ) pre_{find(i)} prefind(i) 可以直接连到 p r e f i n d ( j ) pre_{find(j)} prefind(j) 上，这样就实现了合并。
那么查询其实就是求从 i i i 到 j j j 的节点数，因为有 d i s dis dis 记录两点到第一个点的距离，就可以直接转化为求 a b s ( d i s i − d i s j ) abs(dis_i-dis_j) abs(disi−disj)。
end.
Code
#include<bits/stdc++.h> using namespace std; char f; int t,a,b,x,y,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>>a>>b; 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){
puts("-1"); } else{
printf("%d\n",abs(dis[a]-dis[b])-1); } } } }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/86331.html