题目详情题解（0）讨论（0）提交记录（0）

AT_wtf22_day1_d.Welcome to Tokyo!

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 MM 位编号为 11 到 MM 的竞赛程序员，在接下来的 NN 天内将访问东京。第 ii 位竞赛程序员会在第 LiL_i 天到第 RiR_i 天（1≤Li≤Ri≤N1 \leq L_i \leq R_i \leq N）期间停留在东京。

maroon 君计划与他们举办聚餐。如果在第 xx 天（1≤x≤N1 \leq x \leq N）举办聚餐，则可以与所有满足 Li≤x≤RiL_i \leq x \leq R_i 的竞赛程序员 ii 成为朋友。

对于每个 k=1,2,⋯ ,Nk=1,2,\cdots,N，请解决以下问题：

  • 如果恰好举办 kk 次聚餐，最多能与多少位竞赛程序员成为朋友？

输入格式

输入以如下格式从标准输入给出。

NN MM
L1L_1 R1R_1
L2L_2 R2R_2
⋮\vdots
LML_M RMR_M

输出格式

输出 NN 行。第 ii 行输出 k=ik=i 时的答案。

输入输出样例

  • 输入#1

    3 3
1 1
1 2
3 3

    输出#1

    2
3
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

说明/提示

限制条件

  • 1≤N≤1061 \leq N \leq 10^6
  • 1≤M≤1061 \leq M \leq 10^6
  • 1≤Li≤Ri≤N1 \leq L_i \leq R_i \leq N
  • 输入的所有值均为整数。

样例说明 1

  • k=1k=1：如果在第 11 天举办聚餐，可以与竞赛程序员 1,21,2 成为朋友。
  • k=2k=2：如果在第 11 天和第 33 天举办聚餐，可以与竞赛程序员 1,2,31,2,3 成为朋友。
  • k=3k=3：如果在第 1,2,31,2,3 天都举办聚餐，可以与竞赛程序员 1,2,31,2,3 成为朋友。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页