分数: 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