← 返回题目列表

AtCoder · awc0044_c

C. 范围加法

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

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