更有效地找到差异较小的最大区域
finding largest region with small difference more efficiently
有一个由h * w(h, w <= 200)个像素组成的网格，每个像素用一个值表示，我们要找到最大的连续区域。
一个连续的区域是这样定义的：
- Given a point P(x, y), The connected region must include this point.
- There exists reference point R(x, y) of value v, any point in the connected region must be connected to this point. Also, there is a value g_critical(g_critical <= 100000). Let the value of a point in the connected region be v, the difference
of u and v must be smaller or equal than g_critical.
题目是找出最大连通区域的大小。
比如网格。 h = 5, w = 5, g_critical = 3, P(x, y) = (2, 4)
1 3 7 9 2
2 5 6 6 8
3 5 9 3 6
2 7 3 2 9
在这种情况下，粗体区域是最大的连接区域。请注意，在这种情况下，R(x, y) 是在 (2, 3) 或 (2, 2) 处选择的。区域大小为14.
我稍微改写了这个问题，使其更短。所以如果有不明白的地方，请在评论中指出。这个问题也在我们的私人判断中，所以我无法在这里分享问题来源。
我的尝试
我尝试遍历每个单元格，将其视为 R 点并使用 bfs 找到与其相连的连接区域。然后，检查P是否包含在该区域中。
复杂度为O(h * h * w * w)，太大了。那么有什么办法可以优化吗？
我猜也许从 p 开始会有帮助，但我不确定我应该怎么做。也许有某种洪水填充算法允许我这样做？
提前致谢。
以下是一些可能有帮助的启发式方法：
首先在O(h*w*log(h*w))中进行一些预处理：
- 将矩阵值存储在数组中，对其进行排序
- 现在数组中的每个值都是点 R 的可能候选者
- 最大分量也将是 [R-critical, R+critical]
范围内的值
- 所以我们可以用简单的二分搜索来估计组件的大小（在最好的情况下）
现在一些启发式：
- 这次再次按估计的组件大小降序排列数组
- 如果估计大小大于当前找到的最佳大小，现在按此顺序尝试 BFS
有一个时间复杂度为 O(h w √(g_critical) α(h w)) 的算法（其中 α 是反阿克曼函数，在实际应用中是常量），它使用具有“撤消”操作和 Mo 技巧的变体。这个想法是，将区间 [v − g_critical, v] 分解为大约 √g_critical 个长度大约为 √g_critical 的子区间。对于每个子区间 [a, b]，准备一个不相交的集合数据结构，表示允许值为 [b, a + 2 g_critical] 的矩阵的组件。然后对于 [a, b] 中的每个 c，用值位于 [c, b) 和 (a + 2 g_critical, c + 2 g_critical] 中的点扩展不相交集并报告数字P(x,y) 组件中的节点，然后撤消这些操作（保留对结构所做的写入的堆栈，具有原始值；然后弹出每个，写入原始值）。
还有一种您不会喜欢的时间复杂度为 O(h w log(h w)) 的算法，因为它使用动态树。 （Sleator–Tarjan 1985 年基于 splay 树的构造是最简单的并且在这里工作正常。）发布它主要是为了以防它激发更实用的方法。
高级思想是一种动力学算法，它在最多 g_critical + 1 种可能性上“滑动”允许值的区间，重复报告并在包含的连接组件的大小上取最大值P.
为此，我们需要在派生图上维护最大生成森林。给定一个节点加权无向图，通过细分每条边并将每条新边的权重设置为它所关联的旧节点的权重来构造一个新的边加权图。删除图中最轻的节点很简单——所有路径都尽可能避开这些节点，因此新的最大跨度森林将不再有边。要添加不在图中的最轻节点，请尝试一次 link 它们的入射边。如果形成循环，则翻转一个端点，从另一个端点查询路径最小值，然后取消link那个最小值。
为了报告包含 P 的组件的大小，我们需要另一个装饰来捕获每个节点的具体子树（与表示的子树相对）的大小。细节有点粗糙。
有一个由h * w(h, w <= 200)个像素组成的网格，每个像素用一个值表示，我们要找到最大的连续区域。
一个连续的区域是这样定义的：
- Given a point P(x, y), The connected region must include this point.
- There exists reference point R(x, y) of value v, any point in the connected region must be connected to this point. Also, there is a value g_critical(g_critical <= 100000). Let the value of a point in the connected region be v, the difference of u and v must be smaller or equal than g_critical.
题目是找出最大连通区域的大小。
比如网格。 h = 5, w = 5, g_critical = 3, P(x, y) = (2, 4)
1 3 7 9 2
2 5 6 6 8
3 5 9 3 6
2 7 3 2 9
在这种情况下，粗体区域是最大的连接区域。请注意，在这种情况下，R(x, y) 是在 (2, 3) 或 (2, 2) 处选择的。区域大小为14.
我稍微改写了这个问题，使其更短。所以如果有不明白的地方，请在评论中指出。这个问题也在我们的私人判断中，所以我无法在这里分享问题来源。
我的尝试
我尝试遍历每个单元格，将其视为 R 点并使用 bfs 找到与其相连的连接区域。然后，检查P是否包含在该区域中。
复杂度为O(h * h * w * w)，太大了。那么有什么办法可以优化吗？
我猜也许从 p 开始会有帮助，但我不确定我应该怎么做。也许有某种洪水填充算法允许我这样做？
提前致谢。
以下是一些可能有帮助的启发式方法：
首先在O(h*w*log(h*w))中进行一些预处理：
- 将矩阵值存储在数组中，对其进行排序
- 现在数组中的每个值都是点 R 的可能候选者
- 最大分量也将是 [R-critical, R+critical] 范围内的值
- 所以我们可以用简单的二分搜索来估计组件的大小（在最好的情况下）
现在一些启发式：
- 这次再次按估计的组件大小降序排列数组
- 如果估计大小大于当前找到的最佳大小，现在按此顺序尝试 BFS
有一个时间复杂度为 O(h w √(g_critical) α(h w)) 的算法（其中 α 是反阿克曼函数，在实际应用中是常量），它使用具有“撤消”操作和 Mo 技巧的变体。这个想法是，将区间 [v − g_critical, v] 分解为大约 √g_critical 个长度大约为 √g_critical 的子区间。对于每个子区间 [a, b]，准备一个不相交的集合数据结构，表示允许值为 [b, a + 2 g_critical] 的矩阵的组件。然后对于 [a, b] 中的每个 c，用值位于 [c, b) 和 (a + 2 g_critical, c + 2 g_critical] 中的点扩展不相交集并报告数字P(x,y) 组件中的节点，然后撤消这些操作（保留对结构所做的写入的堆栈，具有原始值；然后弹出每个，写入原始值）。
还有一种您不会喜欢的时间复杂度为 O(h w log(h w)) 的算法，因为它使用动态树。 （Sleator–Tarjan 1985 年基于 splay 树的构造是最简单的并且在这里工作正常。）发布它主要是为了以防它激发更实用的方法。
高级思想是一种动力学算法，它在最多 g_critical + 1 种可能性上“滑动”允许值的区间，重复报告并在包含的连接组件的大小上取最大值P.
为此，我们需要在派生图上维护最大生成森林。给定一个节点加权无向图，通过细分每条边并将每条新边的权重设置为它所关联的旧节点的权重来构造一个新的边加权图。删除图中最轻的节点很简单——所有路径都尽可能避开这些节点，因此新的最大跨度森林将不再有边。要添加不在图中的最轻节点，请尝试一次 link 它们的入射边。如果形成循环，则翻转一个端点，从另一个端点查询路径最小值，然后取消link那个最小值。
为了报告包含 P 的组件的大小，我们需要另一个装饰来捕获每个节点的具体子树（与表示的子树相对）的大小。细节有点粗糙。