题解

思路

队伍合并具有方向：第一支队伍整体接到第二支队伍尾部。普通并查集只能判断是否同队，无法回答队内距离；需要额外维护每个结点到并查集根的偏移量。

做法

1. tiny：显式队列扫描

用数组保存每支队伍的完整排列。每次操作线性寻找两艘战舰所在队伍和位置；合并时拼接两个数组，询问时计算位置差。

2. medium：维护队伍编号和位置

为每艘战舰记录当前队伍编号与队内位置。合并队伍 $A$ 到 $B$ 尾部时，遍历 $A$ 中所有战舰，给位置加上 $|B|$ 并改写队伍编号，然后追加到 $B$。查询变成 $O(1)$。

3. 支线：所有合并先于询问

用普通并查集找到每支队伍的代表，同时维护链表头尾。合并时把 $B$ 的尾部连到 $A$ 的头部，并令 $A$ 的代表指向 $B$。全部合并结束后，遍历每条最终链一次，写出每艘战舰的队伍与位置，再回答全部询问。

4. 满分：带权并查集

令：

• parent[x] 为并查集父亲；
• size[r] 为根 $r$ 所在队伍大小；
• distance[x] 为 $x$ 到父亲方向的队内位置增量。路径压缩后，它等于 $x$ 到根的偏移量。

执行 M i j 时，设两队根为 $r_i,r_j$。因为 $i$ 所在整队接在 $j$ 所在队尾部，令

$$parent[r_i]=r_j,\qquad distance[r_i]=size[r_j],\qquad size[r_j]\mathrel{+}=size[r_i].$$

查找根时，若原父亲为 $p$，递归压缩后执行

$$distance[x]\mathrel{+}=distance[p],$$

即可保持偏移量的可加性。

对 C i j，若根不同输出 $-1$；否则两舰之间的战舰数为

$$|distance[i]-distance[j]|-1.$$

正确性证明

初始每艘战舰单独成队，根偏移为 $0$，不变量成立。合并时，原第二队占据新队伍前 $size[r_j]$ 个位置，因此第一队中每艘战舰相对新根的偏移恰增加 $size[r_j]$；把这一增量记录在第一队根到第二队根的父边上，保留了所有队内相对顺序。

路径压缩只把多条父边替换成一条到根的边，并把沿途偏移相加，所以绝对位置不变。于是同根两舰偏移之差就是位置距离，减一即为中间战舰数；异根则不在同队。算法正确。

复杂度

• tiny：最坏 $O(T\cdot30000)$ 时间，$O(30000)$ 空间；
• medium：最坏 $O(T\cdot30000)$ 时间，查询 $O(1)$，$O(30000)$ 空间；
• 合并先行支线：$O((T+30000)\alpha(30000))$ 时间，$O(T+30000)$ 空间；
• 满分：$O(T\alpha(30000))$ 时间，$O(30000)$ 空间。