← 返回题目列表

AtCoder · arc130_b

B. 彩色线条

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们有一个 H\times W 网格。最初,正方形未上漆。

您将绘制这些方块。有 C 可用颜色,已编号 1, 2, \ldots, C.

绘画过程将给出为 Q 查询。的 i-第一个查询包含整数 t_i, n_i, c_i,代表以下操作。

  • If t_i = 1:绘制所有方块 n_i-th 行 带颜色 c_i.
  • If t_i = 2:绘制所有方块 n_i-th 栏目 带颜色 c_i.

用颜色绘制正方形 c 使该方块的颜色 Color c,无论其之前的状态如何。

找出每种颜色所绘制的方块数量 1, 2, \ldots, C 整个过程结束后。

约束

  • 2\leq H\leq 10^9
  • 2\leq W\leq 10^9
  • 1\leq C\leq 3\times 10^5
  • 1\leq Q\leq 3\times 10^5
  • t_i\in \{1,2\}
  • 1\leq n_i\leq H if t_i = 1
  • 1\leq n_i\leq W if t_i = 2
  • 1\leq c_i\leq C

输入

输入由标准输入按以下格式给出:

H W C Q
t_1 n_1 c_1
\vdots
t_Q n_Q c_Q

输出

打印一行,其中包含用颜色绘制的方块的数量 1, 2, \ldots, C,之间有空格。


示例输入 1

4 5 6 5
1 1 6
1 3 3
2 2 4
2 4 2
1 1 2

示例输出 1

0 8 3 3 0 0

该过程按如下方式更改方块的颜色。在这里, . 表示未绘制的正方形。

.....   66666   66666   64666   64626   22222
.....   .....   .....   .4...   .4.2.   .4.2.
.....   .....   33333   34333   34323   34323
.....   .....   .....   .4...   .4.2.   .4.2.

示例输入 2

1000000000 1000000000 3 5
1 1 2
1 2 2
1 3 2
1 4 2
1 5 2

示例输出 2

0 5000000000 0