CF1303F Number of Components

给定一个 $n \times m$ 的矩阵，初始时所有元素均为 $0$。我们用 $a_{i, j}$ 表示矩阵第 $i$ 行第 $j$ 列的元素。 如果两个格子有公共边且它们的元素值相等，则称这两个格子是连通的。如果存在一个序列 $s_1, s_2, \ldots, 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. 统计当前矩阵中的连通块数量。 还有一个额外的限制：对于每个 $i \in [1, q-1]$，有 $c_i \le c_{i+1}$。

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n, m \le 300$，$1 \le q \le 2 \times 10^6$），分别表示矩阵的行数、列数和操作数。 接下来 $q$ 行，每行包含三个整数 $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 \times 10^6}{nm} \rceil)$）。对于每个 $i \in [1, q-1]$，有 $c_i \le c_{i+1}$。

输出 $q$ 个整数，第 $i$ 个整数表示执行前 $i$ 次操作后，矩阵中的连通块数量。

由 ChatGPT 4.1 翻译