分数: 400 分
问题陈述
有一个围栏,包括 N 高桥家门前的牌子。板的编号从 1 to N 从左到右。
最初,每块板的颜色编号为 0 (未上漆)。
高桥将表演 M 按顺序重画操作。在 i-th (1 \leq i \leq M) 重画操作,他覆盖了棋盘上的所有棋盘 L_i 登机 R_i (含)带色号 C_i。即使是已经涂漆的木板也会更改为新的色号 C_i.
确定所有重涂操作完成后每块板的最终色号。
约束
- 1 \leq N \leq 5 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
- 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
- 所有输入均为整数。
输入
N M L_1 R_1 C_1 L_2 R_2 C_2 \vdots L_M R_M C_M
第一行包含板数 N 和重画操作的数量 M,用空格分隔。以下每一项 M 行包含,对于 i-第次重绘操作,左端点 L_i,右端点 R_i,以及颜色编号 C_i,用空格分隔。
输出
从板上打印每块板的最终颜色编号 1 登机 N,用空格分隔,在一行上。
示例输入 1
5 3 1 3 2 2 5 4 4 4 7
示例输出 1
2 4 4 7 4
示例输入 2
6 4 3 6 1 1 2 9 2 5 3 6 6 8
示例输出 2
9 3 3 3 3 8
示例输入 3
12 7 1 12 5 3 8 2 6 10 9 2 2 4 11 12 7 5 7 1 9 9 6
示例输出 3
5 4 2 2 1 1 1 9 6 9 7 7
示例输入 4
20 11 1 5 3 6 10 4 11 15 5 16 20 6 4 17 8 2 2 1 19 20 9 7 13 2 1 20 10 5 5 11 10 18 12
示例输出 4
10 10 10 10 11 10 10 10 10 12 12 12 12 12 12 12 12 12 10 10
示例输入 5
1 0
示例输出 5
0