题目理解

我们有一个 $H \times W$ 的网格，每个格子 $(i,j)$ 有一个高度 $T_{i,j}$。比太郎的跳跃能力为 $L$，一次跳跃的规则是：

1. 从高度 $x$ 跳到浮空高度 $x + L + 0.5$
2. 在浮空状态下可以向四个方向移动，但经过的格子高度必须小于浮空高度
3. 最后降落在当前格子的山顶

目标：对于 $Q$ 个查询，计算从 $(A_k,B_k)$ 到 $(C_k,D_k)$ 的最少跳跃次数。

关键观察

1. 跳跃可达性分析

一次跳跃中，从格子 $u$ 出发，可以到达所有满足以下条件的格子 $v$：

• 存在一条从 $u$ 到 $v$ 的路径
• 路径上所有格子的高度都小于 $a[u] + L$

2. 问题转化

这实际上是一个分层图最短路问题：

• 每一层对应不同的跳跃次数
• 边权为跳跃过程中经过的路径上的最大高度

算法思路

核心思想：Kruskal 重构树 + 倍增

代码使用了类似 Kruskal 重构树 的思想来处理可达性关系。

数据结构设计

1. 边集合 ed：存储两种类型的边

   • 类型 0：普通移动边 $(u,v,\max(a[u],a[v]))$
   • 类型 1：跳跃边 $(u,u,a[u]+L)$

2. 并查集 fa：维护连通性

3. 倍增数组 f[i][j]：记录跳跃关系

算法流程

步骤 1：构建边集

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        // 跳跃边：从u跳到u，限制为a[u]+L
        ed[++cnt] = edge{id[i][j], id[i][j], a[id[i][j]] + L, 1};
        
        // 普通移动边：向四个方向
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (在边界内且满足高度条件)
                ed[++cnt] = edge{id[i][j], id[x][y], max(a[u],a[v]), 0};
        }
    }
}

步骤 2：Kruskal 合并

按边权从小到大排序并处理：

sort(ed + 1, ed + 1 + cnt, cmp);

for (int i = 1; i <= cnt; i++) {
    if (ed[i].x != ed[i].y) {
        // 合并两个连通块
        int fx = find(ed[i].x), fy = find(ed[i].y);
        if (fx != fy) {
            // 处理跨连通块的查询
            for (auto p : ask[fy]) {
                if (find(p.se) == fx)
                    Q[p.fi].lim = ed[i].z;  // 记录两点间的瓶颈高度
                ask[fx].push_back(p);
            }
            fa[fy] = fx;
        }
    } else {
        // 处理跳跃边，建立倍增关系
        if (当前连通块的代表元可以跳到ed[i].x)
            f[ed[i].x][0] = 代表元;
    }
}

步骤 3：预处理倍增数组

for (int j = 1; j <= 20; j++)
    for (int i = 1; i <= n * m; i++)
        f[i][j] = f[f[i][j - 1]][j - 1];

步骤 4：回答查询

对于每个查询 $(u,v)$：

1. 如果 $a[u] + L \geq \text{lim}$（两点间的瓶颈高度），则 1 次跳跃可达
2. 否则使用倍增找到需要的最少跳跃次数

int x = Q[i].x, ans = 1;
for (int j = 20; j >= 0; j--)
    if (f[x][j] && a[f[x][j]] + L < Q[i].lim)
        x = f[x][j], ans += (1 << j);
x = f[x][0], ans++;

算法正确性

1. 瓶颈高度计算

通过 Kruskal 过程，当两个点首次连通时，记录连通时的边权，这就是两点路径上的最大高度。

2. 跳跃次数计算

倍增数组 f[i][j] 记录了从 $i$ 出发，经过 $2^j$ 次跳跃后能到达的"跳板"位置。通过二进制拆分找到最少跳跃次数。

时间复杂度

• 边数：$O(HW)$
• 排序：$O(HW \log(HW))$
• 并查集合并：$O(HW \alpha(HW))$
• 查询处理：$O(Q \log(HW))$

总复杂度：$O(HW \log(HW) + Q \log(HW))$

算法标签

• Kruskal
• 并查集
• 倍增数组
• 分层图最短路

总结

这道题的关键在于将跳跃过程建模为分层图，并利用 Kruskal 重构树的性质来高效处理可达性查询。通过将移动和跳跃统一为边，并按照高度排序处理，算法巧妙地解决了复杂的状态转移问题。倍增技术的应用使得查询可以在对数时间内完成，整体算法设计非常精妙。