分数: 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