At Least One

题目描述

你得到了一个整数 $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)$。

输入格式

输入由标准输入按以下格式给出： $N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

按以下格式输出答案： $f(1)$ $f(2)$ $\dots$ $f(M)$

3 5
1 3
1 4
2 5

0 1 3 2 1

1 2
1 2

2 1

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

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 \lt B_i \leq M$ 输入中的所有数值均为整数。以下是所有可能的良好序列的列表。

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

标签: AtCoder|abc260E

来源

AtCoder|abc260E