Paint

题目描述

有一个有 $H$ 行 $W$ 列的网格。最开始，所有格子都被涂成颜色 $0$。 你将按顺序执行如下编号为 $i = 1, 2, \ldots, M$ 的操作。

如果 $T_i = 1$，将第 $A_i$ 行的所有格子重新涂成颜色 $X_i$，即重涂第 $A_i$ 个 行。

如果 $T_i = 2$，将第 $A_i$ 列的所有格子重新涂成颜色 $X_i$，即重涂第 $A_i$ 个 列。

在所有操作完成后，对于格子上存在的每一种颜色 $i$，找出被涂成颜色 $i$ 的格子数量。

输入格式

输入按下列格式从标准输入给出： $H$ $W$ $M$ $T_1$ $A_1$ $X_1$ $T_2$ $A_2$ $X_2$ $\vdots$ $T_M$ $A_M$ $X_M$

输出格式

令 $K$ 为存在被涂成颜色 $i$ 的不同整数 $i$ 的个数。输出 $K + 1$ 行。 第一行应包含值 $K$。 第二行及之后的每一行应包含对于网格上存在的每一种颜色 $i$，颜色编号 $i$ 以及被涂成该颜色的格子数量。 具体地，第 $(i + 1)$ 行（$1 \leq i \leq K$）应包含颜色编号 $c_i$ 和被涂成颜色 $c_i$ 的格子数 $x_i$，按此顺序，用空格分隔。 这里，请按 升序 输出颜色编号。也就是说，保证 c_1 < c_2 < \ldots < c_K。另外要求 x_i > 0。

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

3
0 5
2 4
5 3

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

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

1
10000 1

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

5
6 5
7 5
8 5
9 5
10 5

提示

$1 \leq H, W, M \leq 2 \times 10^5$ $T_i \in \lbrace 1, 2 \rbrace$ $1 \leq A_i \leq H$ 对于每个满足 $T_i = 1$ 的 $i$， $1 \leq A_i \leq W$ 对于每个满足 $T_i = 2$ 的 $i$。 $0 \leq X_i \leq 2 \times 10^5$ 所有输入值都是整数。操作最终会将网格的格子颜色变为如下所示：

最终，有五个格子被涂成颜色 $0$，四个被涂成颜色 $2$，以及三个被涂成颜色 $5$。

标签: AtCoder|abc346E

来源

AtCoder|abc346E