← 返回题目列表

Codeforces · 2158/E

E. 水槽

中文机器翻译题面 查看原题

给您一个包含 $$$n$$$ 行和 $$$m$$$ 列的网格。位于第 $$$i$$$ 行和第 $$$j$$$ 列的每个单元格 $$$(i, j)$$$ 都有一个与其关联的正整数值 $$$a_{i, j}$$$。当且仅当两个单元在网格中共享公共边时,它们才是相邻的。

您可以构建 孔 在您选择的单元格。单元格 $$$(x, y)$$$ 是 水槽 当且仅当它有一个洞,或者与 $$$(i, j)$$$ 且 $$$a_{x, y} \ge a_{i, j}$$$ 的水槽相邻。 网格的

的 美女 被定义为您需要构建的最小孔数,以便每个单元都成为一个水槽。

你必须确定这个网格的美感。

您还会收到 $$$q$$$ 查询。

在查询中,您将获得三个正整数 $$$r$$$、$$$c$$$ 和 $$$x$$$。单元格 $$$(r, c)$$$ 的当前值减少 $$$x$$$。每次查询后,考虑到尚未构建孔洞,确定网格的美观程度。

请注意,查询是累积的,因此每个查询的影响都会延续到未来的查询。

保证每次查询后每个单元格的值将保持正值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$1 \le n \cdot m \le 2 \cdot 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\cdot 10^5$$$) — 查询数。

以下 $$$q$$$ 行分别包含 $$$3$$$ 整数 — $$$r、c、$$$ 和 $$$x$$$ ($$$1\le r \le n, 1\le c \le m, 1\le x \lt 10^9$$$)。

保证所有测试用例的 $$$n \cdot m$$$ 之和与 $$$q$$$ 之和不超过 $$$2 \cdot 10^5$$$。

保证每次查询后每个单元格的值将保持正值。

输出

对于每个测试用例,打印 $$$q+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
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$$$) 处创建孔。