AT_abc346_e.[ABC346E] Paint

有一个 $H$ 行 $W$ 列的网格，初始时所有格子都被涂成颜色 $0$。

接下来依次进行 $i = 1, 2, \ldots, M$ 次操作：

• 当 $T_i = 1$ 时，将第 $A_i$ 行的所有格子全部涂成颜色 $X_i$。
• 当 $T_i = 2$ 时，将第 $A_i$ 列的所有格子全部涂成颜色 $X_i$。

所有操作结束后，请对于每种最终存在被涂成颜色 $i$ 的格子，求出该颜色的格子的数量。

输入以如下格式从标准输入读入。

$H$ $W$ $M$
$T_1$ $A_1$ $X_1$
$T_2$ $A_2$ $X_2$
$\vdots$
$T_M$ $A_M$ $X_M$

设最终存在被涂成颜色 $i$ 的格子的颜色种类数为 $K$，输出共 $K+1$ 行。

第 $1$ 行输出 $K$。

接下来的第 $2$ 行到第 $K+1$ 行，对于每种存在被涂成颜色 $i$ 的颜色，输出颜色编号 $c_i$ 以及该颜色的格子数量 $x_i$，用空格隔开。

要求颜色编号按升序输出，即 $c_1 < c_2 < \ldots < c_K$。注意 $x_i > 0$。

限制条件

• $1 \leq H, W, M \leq 2 \times 10^5$
• $T_i \in \{1, 2\}$
• 对于 $T_i = 1$，有 $1 \leq A_i \leq H$
• 对于 $T_i = 2$，有 $1 \leq A_i \leq W$
• $0 \leq X_i \leq 2 \times 10^5$
• 所有输入均为整数

样例解释 1

通过操作，网格中每个格子的颜色变化如下：

0000
0000
0000
0000
0000
0000 → 5555 → 5550 → 5550 → 5550
0000
0000
0000
3333
2222

最终，颜色 $0$ 的格子有 $5$ 个，颜色 $2$ 的格子有 $4$ 个，颜色 $5$ 的格子有 $3$ 个。

由 ChatGPT 4.1 翻译