Number of Components

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

有一个初始全为 $0$ 的 $n\times m$ 矩阵。两个有公共边且数值相等的格子相连；若两个格子之间存在一条相连格子序列，则它们属于同一连通块。

依次处理 $q$ 次操作。每次给出 $x_i,y_i,c_i$，把格子 $(x_i,y_i)$ 的值替换为 $c_i$，然后输出整个矩阵的连通块数量。

保证颜色序列单调不降，即 $c_i\le c_{i+1}$。

输入格式

第一行三个整数 $n,m,q$。接下来 $q$ 行每行三个整数 $x_i,y_i,c_i$。

输出格式

输出 $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

数据范围

• $1\le n,m\le300$；
• $1\le q\le2\times10^6$；
• $1\le x_i\le n$，$1\le y_i\le m$；
• $1\le c_i\le\max(1000,\lceil 2\times10^6/(nm)\rceil)$；
• $c_i\le c_{i+1}$。