Distance - 题解

标签与难度

标签: 数据结构, 分块, 广度优先搜索 (BFS), 最短路, 三维空间, 曼哈顿距离, 在线算法难度: 2100

题目大意喵~

一位叫做 Gromah 的冒险家进入了一个 $n \times m \times h$ 的三维立方体空间，喵~ 这个空间里最初什么都没有。接下来会有一系列的操作，总共有 $q$ 个。

操作分为两种类型：

添加标记: (1, x, y, z)，表示在立方体的 (x, y, z) 位置上增加一个标记点。
查询距离: (2, x, y, z)，需要你计算出，在当前所有已存在的标记点中，哪一个距离给定的 (x, y, z) 点的曼哈顿距离最近，并输出这个最短的距离。

两个点 $(x_1, y_1, z_1)$ 和 $(x_2, y_2, z_2)$ 之间的曼哈顿距离定义为： $|x_1 - x_2| + |y_1 - y_2| + |z_1 - z_2|$ 。

你需要帮他们处理所有的查询操作，并按顺序输出结果，这样他们才能得到通关密码，呐！

解题思路分析

喵哈~ 看到这道题，我的猫耳朵立刻就竖起来了！这是一个在三维空间里动态加点和查询最近点的问题，听起来就很有趣，对吧？

最朴素的想法，喵~

我们先来想一个最简单直接的办法。

操作 1 (加点): 来一个点，我们就把它存进一个小本本（比如一个 vector）里。
操作 2 (查询): 要查询点 P 到最近标记点的距离时，我们就翻开小本本，把里面记下的所有标记点 T 都看一遍，一个一个计算 P 和 T 的曼哈顿距离，然后取一个最小值。

这个方法很简单，但是效率怎么样呢？如果已经加了 $N_{add}$ 个点，那么每次查询就要计算 $N_{add}$ 次距离。如果查询次数是 $N_{query}$ ，总的时间复杂度大概是 $O(N_{add} \cdot N_{query})$ 。当 $q$ 很大的时候，这个复杂度会高得让我的尾巴都炸毛了，肯定会超时的说！

换个思路：预处理大法！

查询慢，那我们能不能把查询变快呢？查询一个点到一堆点集合的最短距离，这听起来很像... 最短路问题！

我们可以把整个 $n \times m \times h$ 的立方体看成一个巨大的图。每个小立方体单元 (x, y, z) 是一个节点，它和它上、下、左、右、前、后六个方向相邻的节点都有一条长度为 1 的边。这样，两个点之间的曼哈顿距离，就等于它们在这个图上的最短路长度。

于是，我们可以用 多源广度优先搜索 (Multi-Source BFS) 来解决！

把所有已经存在的标记点作为起始点（源点），将它们全部放入一个队列中，距离设为 0。
运行 BFS，扩展到所有其他点。
这样，我们就可以预处理出立方体中每一个点到最近标记点的距离，并保存在一个 dist 数组里。

当需要查询时，我们只需要 $O(1)$ 的时间直接从 dist 数组里取出答案 dist[x][y][z] 就行了！查询变得飞快，喵~

但是... 这个方法也有个大问题。题目是在线的，也就是说，标记点是一个一个加进来的。每加一个点，我们就得重新跑一遍完整的 BFS 来更新整个 dist 数组。一次 BFS 的复杂度是 $O(n \cdot m \cdot h)$ ，如果加点的操作很多，总时间还是会爆炸。

平衡的艺术：分块大法！

既然纯暴力查询慢，纯预处理更新慢，那我们能不能把它们结合一下，找到一个平衡点呢？当然可以，这就是“分块”思想的魅力所在，喵~

我们可以把标记点分成两类：

“陈年旧点” (Permanent Tags): 已经存在了一段时间，并且我们已经为它们跑过一次大规模 BFS 的点。它们对整个空间所有点的最短距离贡献，都记录在我们的 dist 数组里了。
“新鲜出炉点” (Recent Tags): 最近才新加入的，数量还不多，我们暂时还没为它们更新全局 dist 数组。我们把它们存在一个临时的列表里，比如叫 recent_tags。

现在，我们的策略就清晰了：

对于操作 1 (加点): 我们把新来的点 (x, y, z) 直接丢进 recent_tags 列表。
对于操作 2 (查询): 对于查询点 P(x, y, z)，它的最近标记点要么是“陈年旧点”，要么是“新鲜出炉点”。
- 到最近的“陈年旧点”的距离，我们已经预处理好了，就是 dist[x][y][z]。
- 到最近的“新鲜出炉点”的距离，因为 recent_tags 里的点不多，我们可以用朴素的方法，直接遍历 recent_tags 列表，暴力计算距离并取最小值。
- 最终答案就是这两者中的较小值！

关键问题： recent_tags 列表什么时候会变得“太大”呢？如果它无限增长，查询的暴力部分不就又变慢了吗？所以，我们要给 recent_tags 列表设一个阈值，比如说 BLOCK_SIZE。

当 recent_tags 里的点数达到了 BLOCK_SIZE 时，我们就进行一次 “重构” (Rebuild)。
重构操作就是运行一次多源 BFS。这次 BFS 的源点就是 recent_tags 里的所有点。它会更新全局的 dist 数组，把这些“新鲜”点的影响融入进去。
重构完成后，recent_tags 里的点就光荣地成为了“陈年旧点”，我们就可以清空 recent_tags 列表，准备迎接下一批新点了！

BLOCK_SIZE 该设为多少呢？ 这是一个经典的复杂度平衡问题。设立方体总点数为 $N_{cells} = n \cdot m \cdot h$ ，总操作数为 $Q$ 。

重构的总成本: 每 BLOCK_SIZE 次添加操作触发一次重构，总共约 $Q / \text{BLOCK\_SIZE}$ 次。每次重构是 BFS，成本 $O(N_{cells})$ 。总成本是 $O(\frac{Q}{\text{BLOCK\_SIZE}} \cdot N_{cells})$ 。
查询的总成本: 每次查询都要暴力遍历 recent_tags，其大小最多为 BLOCK_SIZE。 $Q$ 次查询的总成本是 $O(Q \cdot \text{BLOCK\_SIZE})$ 。

为了让总时间最少，我们让这两部分成本大致相等：

\frac{Q}{\text{BLOCK\_SIZE}} \cdot N_{cells} \approx Q \cdot \text{BLOCK\_SIZE}

N_{cells} \approx \text{BLOCK\_SIZE}^2

\text{BLOCK\_SIZE} \approx \sqrt{N_{cells}}

所以，我们把块的大小设置为 $\sqrt{n \cdot m \cdot h}$ 左右是比较理想的。这样，总的时间复杂度就是 $O(Q \sqrt{N_{cells}})$ ，对于本题的数据范围来说，是完全可以接受的，喵~

代码实现

下面就是我根据这个完美的“分块+BFS”思路，精心编写的代码啦！注释写得很详细，希望能帮助你理解每一个细节哦~

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

// 为了方便，我们用一个结构体来表示三维空间中的点
struct Point {
    int x, y, z;
};

// 立方体的尺寸和查询数
int n, m, h, q;
// 块的大小，用于分块策略
int block_size;

// dist数组存储每个点到“陈年旧点”集合的最近曼哈顿距离
// 使用一维数组模拟三维空间，需要坐标转换
std::vector<int> dist;

// 临时存储“新鲜出炉”的标记点
std::vector<Point> recent_tags;

// 定义6个方向的移动向量，用于BFS
const int dx[] = {1, -1, 0, 0, 0, 0};
const int dy[] = {0, 0, 1, -1, 0, 0};
const int dz[] = {0, 0, 0, 0, 1, -1};

// 将三维坐标(x, y, z)转换为一维数组的索引
// 注意：题目坐标从1开始，我们内部处理时可以保持，也可以转为0-based
// 这里保持1-based，数组大小要开够
inline int get_index(int x, int y, int z) {
    return (x - 1) * m * h + (y - 1) * h + z;
}

// “重构”函数，执行多源BFS
void rebuild() {
    if (recent_tags.empty()) {
        return; // 如果没有新点，就不需要重构啦
    }

    std::queue<Point> q_bfs;
    
    // 将所有“新鲜”点作为源点加入队列
    for (const auto& p : recent_tags) {
        int index = get_index(p.x, p.y, p.z);
        // 如果这个点本身距离不是0 (意味着它不是之前的源点)，
        // 把它设为新的源点
        if (dist[index] > 0) {
            dist[index] = 0;
            q_bfs.push(p);
        }
    }

    // 开始多源BFS
    while (!q_bfs.empty()) {
        Point curr = q_bfs.front();
        q_bfs.pop();
        int curr_idx = get_index(curr.x, curr.y, curr.z);

        // 探索6个邻居
        for (int i = 0; i < 6; ++i) {
            int nx = curr.x + dx[i];
            int ny = curr.y + dy[i];
            int nz = curr.z + dz[i];

            // 检查邻居是否在立方体边界内
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && nz >= 1 && nz <= h) {
                int neighbor_idx = get_index(nx, ny, nz);
                // 如果通过当前点可以找到一条更短的路径
                if (dist[neighbor_idx] > dist[curr_idx] + 1) {
                    dist[neighbor_idx] = dist[curr_idx] + 1;
                    q_bfs.push({nx, ny, nz});
                }
            }
        }
    }

    // 重构完成，清空“新鲜”点列表
    recent_tags.clear();
}

int main() {
    // 加速输入输出，是好习惯喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n >> m >> h >> q;

    // 计算总点数和块大小
    long long total_cells = (long long)n * m * h;
    block_size = static_cast<int>(sqrt(total_cells));
    // 防止块太小或太大，设置一个合理的范围
    if (block_size == 0) block_size = 1;

    // 初始化dist数组，所有距离都设为无穷大
    // 数组大小是总点数+1，因为我们用1-based索引
    const int INF = 1e9;
    dist.assign(total_cells + 1, INF);

    for (int i = 0; i < q; ++i) {
        int type, x, y, z;
        std::cin >> type >> x >> y >> z;

        if (type == 1) { // 添加标记
            recent_tags.push_back({x, y, z});
            // 如果“新鲜”点数量达到阈值，就进行重构
            if (recent_tags.size() >= block_size) {
                rebuild();
            }
        } else { // 查询距离
            // 1. 获取到“陈年旧点”的预处理距离
            int ans = dist[get_index(x, y, z)];

            // 2. 暴力计算到“新鲜出炉点”的距离
            for (const auto& p : recent_tags) {
                int current_dist = std::abs(p.x - x) + std::abs(p.y - y) + std::abs(p.z - z);
                ans = std::min(ans, current_dist);
            }
            
            std::cout << ans << "\n";
        }
    }

    return 0;
}

复杂度分析

时间复杂度: $O(Q \sqrt{N \cdot M \cdot H})$
- 设立方体内的总单元格数量为 $N_{cells} = N \cdot M \cdot H$ 。
- 我们最多进行 $Q / \text{BLOCK\_SIZE}$ 次重构操作。每次重构是 BFS，其复杂度为 $O(N_{cells})$ 。总的重构时间为 $O(\frac{Q}{\text{BLOCK\_SIZE}} \cdot N_{cells})$ 。
- 对于 $Q$ 次操作，每次查询操作最多需要遍历大小为 $\text{BLOCK\_SIZE}$ 的临时点集。总的查询时间为 $O(Q \cdot \text{BLOCK\_SIZE})$ 。
- 当 $\text{BLOCK\_SIZE} = \sqrt{N_{cells}}$ 时，总时间复杂度为 $O(Q \sqrt{N_{cells}})$ ，达到了一个很好的平衡。
空间复杂度: $O(N \cdot M \cdot H)$
- 主要的空间开销是 dist 数组，它需要存储立方体中每一个点的信息，所以空间复杂度是 $O(N \cdot M \cdot H)$ 。
- recent_tags 列表和 BFS 队列占用的空间相对较小，不会超过这个量级。

知识点总结

这道题是一道非常经典的分块思想应用题，喵~ 它教会了我们如何在“单次操作成本”和“操作次数”之间做出权衡。

分块 (Square Root Decomposition): 当遇到在线问题，且修改和查询的朴素解法复杂度不均衡时（一个很快，一个很慢），可以考虑分块。通过将操作或数据分为“大块”和“散块”，对大块进行预处理，对散块进行暴力，从而平衡整体复杂度。
多源广度优先搜索 (Multi-Source BFS): 当需要求解一个点到多个目标点集合的最短距离时，可以将所有目标点同时作为源点放入队列开始 BFS。这是图论中一个非常实用的小技巧。
曼哈顿距离与网格图最短路: 在一个没有障碍的网格图中，两点之间的最短路长度就等于它们的曼哈顿距离。BFS 是求解这种无权图最短路的标准算法。
在线问题处理: 与可以读完所有输入再处理的离线问题不同，在线问题需要我们设计一种能够即时响应的数据结构或算法。分块正是在线算法中平衡效率的有力工具。

希望这篇题解能帮到你，如果有任何问题，随时可以再来问我哦，喵~

Distance - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

最朴素的想法，喵~ ​

换个思路：预处理大法！ ​

平衡的艺术：分块大法！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​