← 返回题目列表

AtCoder · abc260_e

H. 至少一个

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

分数: 500 点

问题陈述

给你一个整数 M 和 N 整数对 (A_1, B_1), (A_2, B_2), \dots, (A_N, B_N).
对于所有人 i,它认为 1 \leq A_i \lt B_i \leq M.

一个序列 S 据说是 好的序列 如果满足以下条件:

  • S 是序列的连续子序列 (1,2,3,..., M).
  • 对于所有人 i, S 至少包含以下之一 A_i 和 B_i.

让 f(k) 是可能的良好长度序列的数量 k.
枚举 f(1), f(2), \dots, f(M).

约束

  • 1 \leq N \leq 2 \times 10^5
  • 2 \leq M \leq 2 \times 10^5
  • 1 \leq A_i \lt B_i \leq M
  • 输入中的所有值都是整数。

输入

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

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

输出

按以下格式打印答案:

f(1) f(2) \dots f(M)

示例输入 1

3 5
1 3
1 4
2 5

示例输出 1

0 1 3 2 1

这是所有可能的好序列的列表。

  • (1,2)
  • (1,2,3)
  • (2,3,4)
  • (3,4,5)
  • (1,2,3,4)
  • (2,3,4,5)
  • (1,2,3,4,5)

示例输入 2

1 2
1 2

示例输出 2

2 1

示例输入 3

5 9
1 5
1 7
5 6
5 8
2 6

示例输出 3

0 0 1 2 4 4 3 2 1