← 返回题目列表

AtCoder · awc0053_d

D. 重新粉刷栅栏

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

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