← 返回题目列表

AtCoder · wtf22_day1_d

D. 欢迎来到东京!

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

分数: 2000 点

问题陈述

有 M 竞争程序员(kyopro-ers)的数量 1 to M,他们将在接下来的 N 天里访问东京。 Kyopro-er i 将从 L_i日待到 R_i- 第天 (1 \leq L_i \leq R_i \leq N).

日。Maroon 正计划与他们举行晚宴。 如果晚宴在 x- 第天 (1 \leq x \leq N日举行,他可以与所有 kyopro-ers 交朋友 i 与 L_i \leq x \leq R_i.

对于每个 k=1,2,\cdots,N,解决以下问题。

  • 如果 Maroon 举办恰好 k 次晚宴,他最多可以结交多少 kyopro-ers。

约束

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq 10^6
  • 1 \leq L_i \leq R_i \leq N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

输出

打印 N 行。 的 i- 第行应包含以下问题的答案 k=i.


示例输入 1

3 3
1 1
1 2
3 3

示例输出 1

2
3
3
  • k=1:如果他在第 1天举办晚宴,他可以与 kyopro-ers 第 1 和 2.
  • k=2:如果他在第 1-st 和 3天结为朋友。 1, 2,和 3.
  • k=3:如果他在第 1-st, 2-nd,和 3天结为朋友。 1, 2,和 3.

示例输入 2

4 4
1 1
2 2
3 3
4 4

示例输出 2

1
2
3
4

示例输入 3

3 6
1 1
1 2
1 2
2 3
2 3
3 3

示例输出 3

4
6
6

示例输入 4

20 15
15 19
1 8
6 11
3 11
11 17
6 6
16 20
7 11
11 14
2 19
1 3
7 7
6 19
14 15
15 15

示例输出 4

7
11
12
13
14
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15