分数: 366 分
问题陈述
高桥管理一系列 N 整数。序列的元素编号为 1 to N 从左到右,最初所有元素的值为 0.
高桥表演 M 对此序列进行操作。在 i-th 操作,他补充道 1 为索引在之间的所有元素的值 L_i 和 R_i,包括在内。
执行完所有操作后,找到序列中每个元素的值。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
- 所有输入均为整数
输入
N M L_1 R_1 L_2 R_2 \vdots L_M R_M
- 第一行包含序列中的元素数量 N 和操作次数 M,用空格分隔。
- 的 (1 + i)第行 (1 \leq i \leq M) 包含左端点 L_i 和右端点 R_i 的间隔 i第一个操作,以空格分隔。
输出
打印 N 单行上用空格分隔的整数。的 i- 第一个整数 (1 \leq i \leq N) 代表的值 i- 执行完所有操作后序列的第一个元素。
示例输入 1
5 3 1 3 2 5 3 4
示例输出 1
1 2 3 2 1
示例输入 2
10 5 1 5 3 8 6 10 1 10 4 6
示例输出 2
2 2 3 4 4 4 3 3 2 2
示例输入 3
20 10 1 20 3 15 5 10 7 8 1 1 20 20 2 19 10 15 12 18 6 14
示例输出 3
2 2 3 3 4 5 6 6 5 6 5 6 6 6 5 3 3 3 2 2