题目大意

给定一个 $N \times N$ 的网格，每个格子 $(i,j)$ 有一棵树，具有：

初始高度 $h_{i,j}$

生长速度 $v_{i,j}$

在任意时间 $t \geq 0$ 时，树的高度为：

$height(i,j,t)=h i,j ​ +v i,j ​ ⋅t$

两棵树相邻当且仅当它们在网格中上下左右相邻。当相邻的树在某个时刻高度相等时，它们属于同一个连通块。

目标：在所有 $t \geq 0$ 的时间中，找出连通块大小的最大值。

算法思路

问题分析

这是一个动态连通性问题，但时间 $t$ 是连续的。直接枚举所有时间点显然不可行。

关键洞察

虽然时间是连续的，但树的高度相等事件只发生在离散的时间点上。

核心观察

对于相邻的两棵树 $(i,j)$ 和 $(x,y)$，它们高度相等的时间 $t$ 满足：

$h_{i,j} + v_{i,j} \cdot t = h_{x,y} + v_{x,y} \cdot t$

整理得：

$(v_{i,j} - v_{x,y}) \cdot t = h_{x,y} - h_{i,j}$ ​

情况分析

$v_{i,j} = v_{x,y}$：

如果 $h_{i,j} = h_{x,y}$：任意时刻高度都相等（永久连接）

否则：永远不相等

$v_{i,j} \neq v_{x,y}$：

$t = \frac{h_{x,y} - h_{i,j}}{v_{i,j} - v_{x,y}}$

仅当 $t \geq 0$ 时有效

用最简分数 $(p,q)$ 表示，避免浮点数精度问题

算法流程

1. 初始化

将二维网格坐标映射为一维编号

初始化并查集，每个树独立成块

记录每个连通块的大小

2. 永久连接处理

遍历所有相邻树对：

如果 $h_{i,j} = h_{x,y}$ 且 $v_{i,j} = v_{x,y}$

立即在并查集中合并

更新最大连通块大小

3. 事件生成

对于其他相邻树对：

计算有效相遇时间 $t \geq 0$

表示为最简分数 $(p,q)$

记录事件：(时间分数, 树对)

4. 事件处理

将所有事件按时间排序

对每个不同的时间点：

合并该时刻所有相遇的树对

更新最大连通块大小

撤销合并（回到该时间点前的状态）

关键技术细节

带撤销的并查集 记录操作：合并时记录被合并的节点

路径压缩受限：使用按秩合并，不路径压缩以支持撤销

撤销栈：保存合并操作序列，按需回溯

分数处理

用 $\frac{p}{q}$ 表示时间，$p,q$ 为互质整数

避免浮点数精度问题

自定义比较函数用于排序

事件分组

相同时间的事件一起处理

确保该时间点的完整连通性状态

复杂度分析

事件数量：$O(N^2)$（每个相邻边最多一个事件）

排序：$O(N^2 \log N)$

并查集操作：$O(N^2 \alpha(N))$

空间复杂度：$O(N^2)$

总结

本题展示了处理连续时间动态连通性问题的有效方法：

离散化思维：将连续时间问题转化为离散事件序列

事件驱动：只在关键时间点计算连通性

可撤销数据结构：支持状态回溯，避免重复计算

精确计算：使用分数避免浮点误差

这种"事件驱动 + 可撤销并查集"的框架具有通用性，可应用于其他随时间变化的图连通性问题，如动态网络、物理模拟等。关键在于识别出状态变化的离散时刻，并高效模拟这些时刻的系统行为。