102604: [AtCoder]ABC260 E - At Least One
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Score : $500$ points
Problem Statement
You are given an integer $M$ and $N$ pairs of integers $(A_1, B_1), (A_2, B_2), \dots, (A_N, B_N)$.
For all $i$, it holds that $1 \leq A_i \lt B_i \leq M$.
A sequence $S$ is said to be a good sequence if the following conditions are satisfied:
- $S$ is a contiguous subsequence of the sequence $(1,2,3,..., M)$.
- For all $i$, $S$ contains at least one of $A_i$ and $B_i$.
Let $f(k)$ be the number of possible good sequences of length $k$.
Enumerate $f(1), f(2), \dots, f(M)$.
Constraints
- $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$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$
Output
Print the answers in the following format:
$f(1)$ $f(2)$ $\dots$ $f(M)$
Sample Input 1
3 5 1 3 1 4 2 5
Sample Output 1
0 1 3 2 1
Here is the list of all possible good sequences.
- $(1,2)$
- $(1,2,3)$
- $(2,3,4)$
- $(3,4,5)$
- $(1,2,3,4)$
- $(2,3,4,5)$
- $(1,2,3,4,5)$
Sample Input 2
1 2 1 2
Sample Output 2
2 1
Sample Input 3
5 9 1 5 1 7 5 6 5 8 2 6
Sample Output 3
0 0 1 2 4 4 3 2 1
Input
题意翻译
给你$M$和$N$对整数$(A_1, B_1), (A_2, B_2)\ldots(A_n,B_n)$。 对于所有的$i$,保证$1 \le A_i \le B_i \le M$。 如果序列$S$满足以下条件,序列$S$将被称为“好序列”: - 序列$S$是序列$(1,2,3 \ldots M)$的连续子序列。 - 对于所有的$i$,$S$至少包含$A_i$和$B_i$的其中一个 令$f(k)$为长度为$k$的“好序列”的总数,请求出$f(1),f(2) \ldots f(M)$并输出Output
得分: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