分数: 450 点
问题陈述
有一个网格 H 行和 W 列。最初,所有单元格都涂上颜色 0.
您将按顺序执行以下操作 i = 1, 2, \ldots, M.
-
If T_i = 1,重新绘制所有单元格 A_i-th 行 有颜色 X_i.
-
If T_i = 2,重新绘制所有单元格 A_i-th 栏目 有颜色 X_i.
所有操作完成后,对于每种颜色 网格上存在的 i ,找到涂有颜色的单元格数量 i.
约束
- 1 \leq H, W, M \leq 2 \times 10^5
- T_i \in \lbrace 1, 2 \rbrace
- 1 \leq A_i \leq H 对于每个 i 这样 T_i = 1,
- 1 \leq A_i \leq W 对于每个 i 这样 T_i = 2.
- 0 \leq X_i \leq 2 \times 10^5
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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 和单元格数量 x_i 涂上颜色 c_i,按此顺序,用空格分隔。
在这里,打印颜色编号 按升序排列。也就是说,确保 c_1 < c_2 < \ldots < c_K。另请注意 x_i > 0 为必填项。
示例输入 1
3 4 4 1 2 5 2 4 0 1 3 3 1 3 2
示例输出 1
3 0 5 2 4 5 3
这些操作将更改网格中单元格的颜色,如下所示:
0000 0000 0000 0000 0000 0000 → 5555 → 5550 → 5550 → 5550 0000 0000 0000 3333 2222
最终,有五个单元格被涂上颜色 0,四色同色 2,以及三个带颜色的 5.
示例输入 2
1 1 5 1 1 1 1 1 10 2 1 100 1 1 1000 2 1 10000
示例输出 2
1 10000 1
示例输入 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