← 返回题目列表

Codeforces · 1303/F

F. 组件数量

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

给定一个矩阵 $$$n \times m$$$,最初用零填充。我们将 $$$a_{i, j}$$$ 定义为矩阵的第 $$$i$$$ 行和第 $$$j$$$ 列中的元素。

如果矩阵的两个单元共享一条边,则它们是相连的,并且这些单元中的元素相等。如果存在序列 $$$s_1$$$, $$$s_2$$$, ..., $$$s_k$$$,其中 $$$s_1$$$ 是第一个单元,$$$s_k$$$ 是第二个单元,并且对于每个 $$$i \in [1, k - 1]$$$、$$$s_i$$$ 和 $$$s_{i + ,则矩阵的两个单元属于同一连通分量1}$$$已连接。

您将获得 $$$q$$$ 形式的查询 $$$x_i$$$ $$$y_i$$$ $$$c_i$$$ ($$$i \in [1, q]$$$)。对于每个此类查询,您必须执行以下操作:

1. 将元素$$$a_{x, y}$$$替换为$$$c$$$;
2. 计算矩阵中连通分量的数量。

还有一个额外的约束:对于 [1, q - 1]$$$ 中的每个 $$$i \, $$$c_i \le c_{i + 1}$$$。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n, m \le 300$$$, $$$1 \le q \le 2 \cdot 10^6$$$) — 分别是行数、列数和查询数。

接下来是 $$$q$$$ 行,每行代表一个查询。第 $$$i$$$ 行包含三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$c_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$, $$$1 \le c_i \le \max(1000, \lceil \frac{2 \cdot 10^6}{nm} \rceil)$$$)。对于每个 $$$i \in [1, q - 1]$$$,$$$c_i \le c_{i + 1}$$$。

输出

打印 $$$q$$$ 整数,其中第 $$$i$$$ 应等于执行第一个 $$$i$$$ 查询后矩阵中的分量数。

示例

输入 #1

3 2 10
2 1 1
1 2 1
2 2 1
1 1 2
3 1 2
1 2 2
2 2 2
2 1 2
3 2 4
2 1 5

输出 #1

2
4
3
3
4
4
4
2
2
4