题解：战舰队列问题

题目背景与问题分析

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

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

问题描述

杨威利将巴米利恩星域战场划分成 $30000$ 列，每列依次编号为 $1,2,\dots,30000$。他把自己的战舰也依次编号为 $1,2,\dots,30000$，让第 $i$ 号战舰处于第 $i$ 列，形成"一字长蛇阵"。

两种操作指令：

• 合并指令 M i j：将第 $i$ 号战舰所在的整个战舰队列接至第 $j$ 号战舰所在的战舰队列的尾部
• 查询指令 C i j：询问第 $i$ 号战舰与第 $j$ 号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰

数据范围：

• $1 \leq T \leq 5 \times 10^5$（指令总数）
• $1 \leq i,j \leq 30000$（战舰编号）

算法核心思路

这个问题本质上是动态维护多个队列的合并操作，并支持查询两个元素在队列中的相对位置。我们可以使用带权并查集来高效解决。

带权并查集设计

在标准的并查集基础上，我们维护两个额外的数组：

int fa[maxn];    // 父节点数组，fa[i]表示战舰i的父节点
int siz[maxn];   // 队列大小，siz[i]表示以i为根的队列包含的战舰数量  
int dis[maxn];   // 距离数组，dis[i]表示战舰i到其所在队列根节点的距离

初始化：

for (int i = 1; i <= 30000; ++i) {
    fa[i] = i;    // 每个战舰初始时自成一体
    siz[i] = 1;   // 每个队列初始大小为1
    dis[i] = 0;   // 到自己的距离为0
}

核心操作详解

1. 查找操作（路径压缩）

int fin(int x) {
    if (fa[x] != x) {
        int root = fin(fa[x]);    // 递归找到根节点
        dis[x] += dis[fa[x]];     // 更新x到根节点的距离
        fa[x] = root;             // 路径压缩，直接指向根节点
    }
    return fa[x];
}

数学原理：

• 设当前节点 $x$ 的父节点为 $p$，根节点为 $r$
• 在路径压缩前：$dis[x]$ 表示 $x$ 到 $p$ 的距离
• 路径压缩后：需要更新为 $x$ 到 $r$ 的距离
• 由于 $dis[p]$ 已经更新为 $p$ 到 $r$ 的距离
• 所以 $x$ 到 $r$ 的距离 = $x$ 到 $p$ 的距离 + $p$ 到 $r$ 的距离
• 即：$dis[x]_{new} = dis[x]_{old} + dis[p]$

2. 合并操作

void uni(int x, int y) {
    int xr = fin(x), yr = fin(y);  // 找到x和y的根节点
    
    if (xr != yr) {
        fa[xr] = yr;               // 将xr的父节点设为yr
        dis[xr] = siz[yr];         // xr到新根yr的距离为原yr队列的大小
        siz[yr] += siz[xr];        // 更新新队列的大小
    }
}

合并过程图示：

合并前：
队列Y: [y1, y2, ..., ym]   (大小 = siz[yr] = m)
队列X: [x1, x2, ..., xn]   (大小 = siz[xr] = n)

合并后：
新队列: [y1, y2, ..., ym, x1, x2, ..., xn]

xr到yr的距离 = 原Y队列的大小 = m
新队列大小 = m + n

数学推导：

• 设队列 $Y$ 有 $m$ 艘战舰，队列 $X$ 有 $n$ 艘战舰
• 将 $X$ 接到 $Y$ 尾部后，$X$ 的根节点 $xr$ 到新根 $yr$ 的距离应为 $m$
• 因为 $xr$ 前面有整个 $Y$ 队列的 $m$ 艘战舰

3. 查询操作

if (op == 'C') {
    int xr = fin(x), yr = fin(y);
    if (xr != yr) {
        printf("-1\n");  // 不在同一队列
    } else {
        printf("%d\n", abs(dis[x] - dis[y]) - 1);
    }
}

距离计算原理：

• 设战舰 $i$ 到根节点的距离为 $d_i$，战舰 $j$ 到根节点的距离为 $d_j$
• 它们在队列中的相对距离为 $|d_i - d_j|$
• 它们之间的战舰数量为 $|d_i - d_j| - 1$（不包括 $i$ 和 $j$ 本身）

示例：

队列: [A, B, C, D, E]  (根节点为A)
dis[A]=0, dis[B]=1, dis[C]=2, dis[D]=3, dis[E]=4

C和E之间的战舰数量 = |dis[C] - dis[E]| - 1 = |2-4| - 1 = 1 (只有战舰D)

时间复杂度分析

• 查找操作：使用路径压缩后，近似 $O(\alpha(n))$，其中 $\alpha$ 是反阿克曼函数
• 合并操作：同样为 $O(\alpha(n))$
• 总体复杂度：$O(T \cdot \alpha(n))$，其中 $T \leq 5 \times 10^5$

对于 $n = 30000$，$\alpha(n) \leq 4$，因此算法效率很高，能够处理最大数据规模。

完整代码实现

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 30010;  // 稍大于30000以防越界

int fa[maxn];    // 父节点数组
int siz[maxn];   // 队列大小
int dis[maxn];   // 到根节点的距离

// 查找操作，带路径压缩和距离更新
int fin(int x) {
    if (fa[x] != x) {
        int root = fin(fa[x]);
        dis[x] += dis[fa[x]];  // 关键：更新到根节点的距离
        fa[x] = root;          // 路径压缩
    }
    return fa[x];
}

// 合并操作
void uni(int x, int y) {
    int xr = fin(x), yr = fin(y);
    
    if (xr != yr) {
        fa[xr] = yr;
        dis[xr] = siz[yr];     // xr到新根的距离为原yr队列大小
        siz[yr] += siz[xr];    // 更新新队列大小
    }
}

int main() {
    int T;
    scanf("%d", &T);
    
    // 初始化
    for (int i = 1; i <= 30000; ++i) {
        fa[i] = i;
        siz[i] = 1;
        dis[i] = 0;
    }
    
    while (T--) {
        char op;
        int x, y;
        scanf(" %c%d%d", &op, &x, &y);
        
        if (op == 'M') {
            // 合并指令：将x所在队列接到y所在队列尾部
            uni(x, y);
        } else {
            // 查询指令
            int xr = fin(x), yr = fin(y);
            if (xr != yr) {
                printf("-1\n");  // 不在同一队列
            } else {
                // 在同一队列，计算中间战舰数量
                printf("%d\n", abs(dis[x] - dis[y]) - 1);
            }
        }
    }
    
    return 0;
}

样例详细分析

输入：

4
M 2 3
C 1 2  
M 2 4
C 4 2

执行过程：

1. 初始状态：

   队列1: [1] (dis[1]=0, siz=1)
   队列2: [2] (dis[2]=0, siz=1) 
   队列3: [3] (dis[3]=0, siz=1)
   队列4: [4] (dis[4]=0, siz=1)
   

2. M 2 3：将队列2接到队列3尾部

   队列3: [3, 2] (dis[3]=0, dis[2]=1, siz=2)
   其他队列不变
   

3. C 1 2：战舰1和2不在同一队列，输出 -1

4. M 2 4：将队列2,3接到队列4尾部

   队列4: [4, 3, 2] (dis[4]=0, dis[3]=1, dis[2]=2, siz=3)
   

5. C 4 2：战舰4和2在同一队列

   • dis[4] = 0, dis[2] = 2
   • 中间战舰数量 = |0-2| - 1 = 1（战舰3）
   • 输出 1

算法正确性证明

不变性条件：

1. 对于队列中的任意战舰 $i$，$dis[i]$ 准确表示 $i$ 到队首的距离
2. 合并操作后，新队列的距离关系保持正确
3. 路径压缩后，距离信息得到正确更新

数学归纳：

• 初始时每个战舰独立成队，条件成立
• 每次合并操作保持条件成立
• 每次查找操作通过路径压缩保持条件成立

因此算法能够正确维护所有队列结构，并准确回答查询。

这种带权并查集的解法巧妙地将队列的相对位置信息编码到距离数组中，通过路径压缩保证效率，是处理此类动态合并查询问题的经典方法。