汇点 题解

思路

先考虑静态网格。把值相等且相邻的格子缩成一个等值连通块。若一个块相邻于值更小的格子，就可以从更低处的汇点传播到该块；否则，这个块至少需要一个洞。

把等值块按值从小到大看成有向无环关系后，每个没有更低邻块的局部最小块必须打洞，并且从这些块出发可以沿非降值边覆盖所有块。因此美丽值恰好等于局部最小等值连通块的数量。

子任务 1 直接对等值格子做并查集或洪水填充，再统计没有更低邻格的块。

子任务 2 在每次修改后完整重建所有等值块并统计答案。

子任务 3 中所有值始终两两不同，每个等值块只有一个格子。美丽值就是严格局部最小格子的数量。一次修改只会改变该格子及其至多四个邻格的局部最小状态。

满分数据允许大等值块。直接维护当前等值块会遇到单点离开后分裂的问题。关键是所有修改只会让值减小：一个被新低值格子切开的旧等值块，其所有碎片都已经拥有更低邻格，以后永远不再需要洞。因此可以保留历史连接，并为每次修改创建新的版本节点。

做法

并查集中，每个根维护：

• 该版本连通块的共同值；
• 该块是否仍需要一个洞。

初始时，每个格子建立一个节点。若它有更低邻格，则标记为不需要洞；再合并相邻且值相等的节点。合并后的标记取逻辑与，因为一个等值块只要有任意更低邻格就不需要洞。

修改格子 $v$，新值为 $x$。只需收集下列至多五个旧根：$v$ 的当前版本根与四个邻格当前版本根。

先从答案中减去这些不同根的旧贡献。随后：

1. 对所有块值大于 $x$ 的受影响旧根，把“需要洞”标记清零，因为它们现在相邻于新的更低格子；
2. 为 $v$ 创建值为 $x$ 的新版本节点；
3. 若存在值小于 $x$ 的邻格，新节点不需要洞；否则暂时需要洞；
4. 把新节点与值同为 $x$ 的受影响根合并；
5. 更新 $v$ 指向的新版本节点，并把当前至多五个不同根的贡献重新加入答案。

历史版本节点不会再作为格子的当前节点，但保留在并查集中。旧等值块即使被分裂也已经因为新低格子的出现而永久失去贡献，保留其历史合并不会造成错误。

正确性证明

静态结论已经说明，美丽值等于当前局部最小等值块的数量。

归纳假设修改前，并查集每个当前等值块所属的根都正确记录其是否为局部最小块，答案是这些根标记之和。

一次修改只改变格子 $v$ 的值。除 $v$ 原块及四个邻格所在块外，其他块的值、相邻关系和局部最小状态均不变。

对受影响旧块，只有块值大于新值 $x$ 时会新获得一个更低邻格 $v$，程序恰好清除其贡献。块值小于等于 $x$ 时不会因为本次修改新增更低邻格，旧状态保持正确。

新版本节点代表修改后的 $v$。它有更低邻格当且仅当邻格最小值小于 $x$；程序据此初始化标记。随后与所有相邻且值同为 $x$ 的当前块合并，逻辑与准确表示合并后的整个等值块是否完全没有更低邻格。

若旧等值块因 $v$ 离开而在当前网格中分裂，则每个剩余部分都与更低的 $v$ 相邻或属于已经清零的历史块；其贡献不可能恢复。由于以后只有减小操作，保留历史合并是安全的。

程序先删除所有受影响旧根贡献，再加入更新后的不同根贡献，未受影响根保持不变。因此归纳成立，每次输出都等于当前局部最小等值块数，即正确的美丽值。

复杂度分析

每次修改只创建一个节点并访问至多五个并查集根，除去小常数集合去重，均摊复杂度为 $O(\alpha(nm+q))$。

每组数据总时间复杂度为 $O(nm+q\alpha(nm+q))$，空间复杂度为 $O(nm+q)$。所有测试组的总规模满足题目给出的聚合限制。