题目分析

问题本质

在 $n \times m$ 的网格上，初始有若干苹果树。每年：

1. 查询一个新位置到所有现有苹果树的最近距离平方
2. 将该位置变为新的苹果树

需要高效处理 $g$ 次这样的操作。

核心挑战

1. 动态更新：苹果树集合不断增长
2. 高效查询：$g$ 可达 $10^5$，需要快速最近邻查询
3. 网格规模：$n \times m \leq 250,000$

关键观察

距离性质

• 只需要距离平方，避免浮点运算：$d^2 = (x_1-x_2)^2 + (y_1-y_2)^2$
• 曼哈顿距离的BFS只能得到近似解，需要欧几里得距离

网格结构优势

网格是规则结构，可以利用BFS的性质来维护最近距离。

算法框架

解法：动态多源BFS

核心思想：维护每个格子到最近苹果树的距离平方。

数据结构：

• dist[i][j]：位置 $(i,j)$ 到最近苹果树的距离平方
• 队列用于BFS

初始化：

1. 扫描初始网格，将所有苹果树位置加入队列，dist 设为 $0$
2. 执行多源BFS，计算所有位置到初始苹果树的最近距离

每年处理：

1. 查询：直接读取 dist[x_i][y_i] 作为答案
2. 更新：
   • 将新苹果树位置 $(x_i,y_i)$ 加入队列
   • 从该位置开始BFS，更新周围格子的距离
   • 如果找到更近的距离，更新 dist 并继续传播

算法细节

BFS更新策略

当在位置 $(x,y)$ 添加新苹果树时：

• 从 $(x,y)$ 开始BFS
• 对于每个访问的位置 $(nx,ny)$，计算新距离：$d_{new} = (x-nx)^2 + (y-ny)^2$
• 如果 $d_{new} < dist[nx][ny]$，则更新并继续BFS
• 否则停止该方向的搜索（因为距离只会更大）

剪枝优化

距离单调性：在BFS过程中，距离平方是单调递增的，一旦发现当前距离不小于已有距离，该方向后续位置都不需要更新。

方向性剪枝：由于距离是欧几里得距离，可以按距离递增顺序处理位置。

复杂度分析

时间复杂度

• 初始化：一次多源BFS，$O(nm)$
• 每次操作：最坏情况下BFS整个网格，$O(nm)$
• 总复杂度：$O(g \cdot nm)$，最坏 $10^5 \times 250,000 = 2.5 \times 10^{10}$

但实际运行中：

• 新苹果树通常不会触发全局更新
• 剪枝会大幅减少搜索范围
• 在随机数据下表现良好

空间复杂度

• dist 数组：$O(nm)$
• BFS队列：$O(nm)$
• 总空间：$O(nm)$

特殊情况处理

初始无苹果树

题目保证初始至少有一棵苹果树，无需处理。

边界处理

网格边界需要特殊处理，避免数组越界。

重复位置

如果苹果落在已有苹果树位置，距离为 $0$。

优化策略

增量更新

每次只从新苹果树开始BFS，利用已有距离信息进行剪枝。

距离比较

直接比较距离平方，避免开方运算。

队列管理

使用双端队列或优先队列可能更好，但普通队列在实际中通常足够。

替代算法分析

暴力查询

• 每次查询遍历所有苹果树
• 复杂度：$O(g \cdot \text{苹果树数量})$，最坏 $O(g^2)$，不可行

KD树

• 维护苹果树的空间索引
• 查询：$O(\log g)$
• 插入：$O(\log g)$
• 但实现复杂，常数较大

网格分块

• 将网格分块，每块维护最近苹果树
• 查询时检查周围块
• 实现相对简单，但效果不如BFS直接

实际性能考虑

对于 $n,m \leq 500$，$g \leq 10^5$：

• 最坏情况不可行，但实际数据通常不会卡最坏
• 如果新苹果树分布均匀，每次BFS范围较小
• 如果新苹果树集中在某区域，可能退化

总结

本题的核心在于利用网格结构和BFS性质动态维护最近距离。动态多源BFS方法虽然理论最坏复杂度较高，但在实际数据中通过剪枝可以高效运行。关键优化在于利用已有距离信息限制BFS范围，避免不必要的计算。