A16703. Sink
编程题
省选/NOI-
知识点
题目描述
给你一个包含 $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$。每次查询后，你需要输出在没有打洞的情况下当前网格的美丽值。
注意查询具有累积效果，每次查询对后续查询仍然有效。
保证每次查询后每个单元格的值依然为正整数。
你可以选择在任意的单元格上打洞。如果某个单元格 $(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$。
每个测试用例的第一行包含两个整数 $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
1 1 2 4 4 1 2 1 1 2 3 1 2
说明/提示
对于第一个测试用例：
- 初始情况下，可以在 $(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)$ 处各打一个洞。
- 初始情况下，可以在 $(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)$ 处各打一个洞。