CF2158E Sink

给你一个包含 $n$ 行 $m$ 列的网格。每个位于第 $i$ 行第 $j$ 列的单元格 $(i, j)$ 都有一个正整数值 $a_{i,j}$。如果两个单元格在网格中共享一条边，则它们是相邻的。 你可以选择在任意的单元格上打洞。如果某个单元格 $(x, y)$ 本身有洞，或者它与某个满足 $a_{x, y} \ge a_{i, j}$ 的“汇点”（即带洞的单元格或相邻已有汇点的单元格）$(i,j)$ 相邻，那么该单元格$(x,y)$也称为汇点。 网格的美丽值被定义为：你最少需要打多少个洞，才能使所有单元格都成为汇点。 你需要计算该网格的美丽值。 此外，给你 $q$ 个查询。 在每个查询中，给定三个正整数 $r$，$c$ 和 $x$，表示将当前单元格 $(r,c)$ 的值减少 $x$。每次查询后，你需要输出在没有打洞的情况下当前网格的美丽值。 注意查询具有累积效果，每次查询对后续查询仍然有效。 保证每次查询后每个单元格的值依然为正整数。

每个测试用例包含多组数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \times 10^5$，$1 \le n \cdot m \le 2 \times 10^5$），分别表示网格的行数和列数。 接下来的 $n$ 行，每行 $m$ 个整数；第 $i$ 行的第 $j$ 个数 $a_{i, j}$ 表示第 $i$ 行第 $j$ 列单元格的数值（$1 \le a_{i, j} \le 10^9$）。 接下来一行包含一个整数 $q$（$0 \le q \le 2 \times 10^5$），表示查询次数。 接下来的 $q$ 行，每行包含三个整数 $r, c, x$（$1 \le r \le n, 1 \le c \le m, 1 \le x < 10^9$）。 保证所有测试用例中 $n \cdot m$ 及所有 $q$ 的总和不超过 $2 \times 10^5$。 保证每次查询后每个单元格的值都大于 $0$。

对于每个测试用例，输出 $q+1$ 行。 第一行输出初始网格的美丽值。 然后每次查询后各输出一行，输出当前网格的美丽值。

对于第一个测试用例： - 初始情况下，可以在 $(1,1)$ 处打一个洞。 - 第一次查询后，可以在 $(1,1)$ 处打一个洞。 - 第二次查询后，可以在 $(1,1)$ 和 $(1,3)$ 处各打一个洞。 对于第二个测试用例： - 初始情况下，可以在 $(1,2)$、$(2,1)$、$(2,3)$ 和 $(3,2)$ 处各打一个洞。 - 第一次查询后，可以在 $(1,2)$、$(2,1)$、$(2,3)$ 和 $(3,2)$ 处各打一个洞。 - 第二次查询后，可以在 $(2,2)$ 处打一个洞。 - 第三次查询后，可以在 $(2,2)$ 和 $(3,3)$ 处各打一个洞。 由 ChatGPT 5 翻译