Colorful
源文件名:colorful.cpp
输入文件名:colorful.in
输出文件名:colorful.out
问题描述:
给定一个H×W的格子,最初的状态是,所有的正方形都没有被标记。
你的任务给这些正方形做标记。有C种颜色可以选择,编号分别说1, 2, . . . , C.
每个标记过程单独一行给出,一共有Q个标记过程。第i次标记过程,包含t_i,n_i,c_i,代表的含义如下:
如果t_i=1:把n_i行的所有正方形标记为颜色c_i
如果t_i=2:把n_i列的所有正方形标记为颜色c_i
把某个正方形标记为颜色C,这个过程会覆盖掉前面所有的标记结果。
经过所有的标记过程后,请打印出每个颜色标记了几个方块?
数据范围:
2≤H≤〖10〗^9
2≤W≤〖10〗^9
1≤C≤3×〖10〗^5
1≤Q≤3×〖10〗^5
t_i∈{1,2}
1≤n_i≤H,如果t_i=1
1≤n_i≤W,如果t_i=2
1≤c_i≤C
输入:
H W C Q
t_1 n_1 c_1
.
.
.
t_Q n_Q c_Q dd
输出:
打印出一行数字,分别对应1,2,… ,C 个颜色标记的方块的数量
样例输入1:
4 5 6 5
1 1 6
1 3 3
2 2 4
2 4 2
1 2
样例输出1:
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
5 2
样例输出2:
0 5000000000 0
谢谢大佬