【题目来源】AcWing238. 银河英雄传说 - AcWing题库【题目描述】有一个划分为N NN列的星际战场各列依次编号为1 , 2 , … , N 1,2,…,N1,2,…,N。有N NN艘战舰也依次编号为1 , 2 , … , N 1,2,…,N1,2,…,N其中第i ii号战舰处于第i ii列。有T TT条指令每条指令格式为以下两种之一M i j表示让第i ii号战舰所在列的全部战舰保持原有顺序接在第j jj号战舰所在列的尾部。C i j表示询问第i ii号战舰与第j jj号战舰当前是否处于同一列中如果在同一列中它们之间间隔了多少艘战舰。现在需要你编写一个程序处理一系列的指令。【输入】第一行包含整数T TT表示共有T TT条指令。接下来T TT行每行一个指令指令有两种形式M i j或C i j。其中M MM和C CC为大写字母表示指令类型i ii和j jj为整数表示指令涉及的战舰编号。【输出】你的程序应当依次对输入的每一条指令进行分析和处理如果是M i j形式则表示舰队排列发生了变化你的程序要注意到这一点但是不要输出任何信息如果是C i j形式你的程序要输出一行仅包含一个整数表示在同一列上第i ii号战舰与第j jj号战舰之间布置的战舰数目如果第i ii号战舰与第j jj号战舰当前不在同一列上则输出− 1 −1−1。【输入样例】4 M 2 3 C 1 2 M 2 4 C 4 2【输出样例】-1 1【核心思想】问题分析给定N NN艘战舰初始各自成一列以及T TT条指令合并两列或查询两艘战舰是否在同一列及间隔数。需要动态维护多列战舰的合并并支持查询同一列中两艘战舰之间的间隔数量。这是一个带权并查集问题关键在于维护每个战舰到所在列队首的相对距离。算法选择带权并查集Extended Union-Find维护每个节点到根节点的距离支持O ( α ( n ) ) O(\alpha(n))O(α(n))的合并与查询路径压缩更新距离在路径压缩时累加父节点到根节点的距离保持相对位置信息集合大小维护siz[x]记录以x xx为根的列的战舰总数用于合并时计算新根的距离关键步骤初始化p[i] isiz[i] 1d[i] 0$每艘战舰自成一列到自身的距离为 0带权查找路径压缩递归查找根节点u find(p[x])更新d[x] d[p[x]]使d[x]表示x xx到根节点的累计距离到队首的战舰间隔数p[x] u路径压缩合并指令M a b将a aa所在列接在b bb所在列尾部pa find(a),pb find(b)若pa ! pbd[pa] siz[pb]a aa所在列的根节点到b bb所在列根节点的距离 b bb列的战舰总数siz[pb] siz[pa]b bb列战舰总数增加p[pa] pb将a aa列的根挂到b bb列的根下面查询指令C a bpa find(a),pb find(b)若pa ! pb输出-1不在同一列若pa pb间隔数 abs(d[a] - d[b]) - 1$两艘战舰之间布置的战舰数目不包括自身时间/空间复杂度时间复杂度O ( T ⋅ α ( N ) ) O(T \cdot \alpha(N))O(T⋅α(N))其中α \alphaα为阿克曼函数反函数近似常数。每次查找或合并操作均摊O ( α ( N ) ) O(\alpha(N))O(α(N))空间复杂度O ( N ) O(N)O(N)并查集父节点数组、距离数组和集合大小数组带权并查集的核心思想相对距离维护d[x]表示x xx到根节点的距离通过路径压缩累加更新保持相对位置信息不丢失合并时设置距离将集合A AA接在集合B BB尾部时A AA的根到B BB的根的距离 B BB的集合大小保证A AA中所有元素到B BB根的距离正确集合大小传递合并后更新siz[pb]为后续合并提供正确的距离基准查询时计算间隔同一集合内两节点的间隔 两者到根的距离之差的绝对值减 1适用于需要维护相对位置/距离的集合合并与查询问题如队列合并、食物链、银河英雄传说等【算法标签】#并查集【代码详解】#includebits/stdc.husingnamespacestd;constintN30005;// 最大战舰数量N 最大为 30000intm;// 指令数量intp[N],siz[N],d[N];// p: 并查集父节点; siz[x]: 以 x 为根的列的战舰总数; d[x]: x 到根节点的战舰间隔数// 带权并查集查找路径压缩同时维护到根节点的距离intfind(intx){if(p[x]!x){intufind(p[x]);// 递归查找根节点d[x]d[p[x]];// 更新 x 到根节点的距离累加父节点到根节点的距离p[x]u;// 路径压缩将 x 直接指向根节点}returnp[x];// 返回根节点}intmain(){cinm;// 读入指令数量for(inti1;iN;i)// 初始化并查集{p[i]i;// 每个战舰自成一个集合初始时每列一艘战舰siz[i]1;// 每列初始战舰数为 1}while(m--)// 依次处理每条指令{charop;// 指令类型M 合并C 查询inta,b;// 涉及的两艘战舰编号cinopab;if(opM)// 合并指令将 a 所在列接在 b 所在列的尾部{intpafind(a),pbfind(b);// 查找 a 和 b 的根节点if(pa!pb)// 若不在同一列才进行合并{d[pa]siz[pb];// a 所在列的根节点到 b 所在列根节点的距离 b 列的战舰数siz[pb]siz[pa];// b 列的战舰总数增加加上 a 列的战舰数p[pa]pb;// 将 a 列的根挂到 b 列的根下面}}else// 查询指令询问 a 和 b 是否在同一列及间隔数{intpafind(a),pbfind(b);// 查找 a 和 b 的根节点if(pa!pb)// 若不在同一列cout-1endl;// 输出 -1else// 若在同一列// 间隔数 |d[a] - d[b]| - 1两艘战舰之间布置的战舰数目不包括自身coutmax(0,abs(d[a]-d[b])-1)endl;}}return0;}【运行结果】4 M 2 3 C 1 2 -1 M 2 4 C 4 2 1