AT_abc260_e [ABC260E] At Least One

题目描述

给定一个整数 $M$ 和 $N$ 个整数对 $(A_1, B_1), (A_2, B_2), \dots, (A_N, B_N)$。
对于所有的 $i$，都有 $1 \leq A_i < B_i \leq M$。

满足以下条件的数列 $S$ 被称为好数列：

• $S$ 是数列 $(1,2,3,\dots,M)$ 的一个连续子序列。
• 对于所有的 $i$，$S$ 至少包含 $A_i$ 或 $B_i$ 中的一个。

记长度为 $k$ 的好数列的个数为 $f(k)$。
请依次输出 $f(1), f(2), \dots, f(M)$。

输入格式

输入通过标准输入按以下格式给出。

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

请按以下格式输出答案。

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

输入输出样例 #1

输入 #1

3 5
1 3
1 4
2 5

输出 #1

0 1 3 2 1

输入输出样例 #2

输入 #2

1 2
1 2

输出 #2

2 1

输入输出样例 #3

输入 #3

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

输出 #3

0 0 1 2 4 4 3 2 1

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $2 \leq M \leq 2 \times 10^5$
• $1 \leq A_i < B_i \leq M$
• 输入的所有值均为整数

样例解释 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)$

由 ChatGPT 4.1 翻译