CFCF2158E.Sink

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

给你一个包含 $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

3
1 4
1 2 3 5
2
1 4 1
1 3 2
3 3
5 1 6
2 9 3
7 4 8
3
2 2 1
2 2 7
3 3 7
3 4
10 10 10 10
10 10 10 10
10 10 11 10
5
3 3 5
2 2 5
2 4 5
2 3 5
1 1 9

输出#1

对于第一个测试用例：

对于第二个测试用例：