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

输入 #1

3 4 4
1 2 5
2 4 0
1 3 3
1 3 2

输出 #1

3
0 5
2 4
5 3

输入输出样例 #2

输入 #2

1 1 5
1 1 1
1 1 10
2 1 100
1 1 1000
2 1 10000

输出 #2

1
10000 1

输入输出样例 #3

输入 #3

5 5 10
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5
2 1 6
2 2 7
2 3 8
2 4 9
2 5 10

输出 #3

5
6 5
7 5
8 5
9 5
10 5

说明/提示

限制条件

• $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 翻译