일차원 게임

면접 대비

시간 제한2초메모리 제한1024 MB

요약

서로 다른 n개의 구간이 주어질 때, 각 구간에서 시작해 포함 관계를 따라 내려가는 경로의 수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 보통10점 중 5점
유형: 정렬, 트리, 동적 계획법
정답자: 아직 제출이 없습니다

문제

보그단이 게임을 하고 있다. 이 게임은 일차원이다. 수평선 위에 $n$ 개의 발판이 놓여 있다. 보그단은 발판 사이를 이동할 수 있다. $i$ 번째 발판은 수평 선분 $[l_i, r_i]$ 이다. 모든 선분은 서로 다르다.

발판 $j$ 가 발판 $i$ 의 내부에 있다는 것은 $l_i \le l_j$ 이고 $r_j \le r_i$ 인 것을 뜻한다.

게임을 시작할 때 보그단은 출발할 발판을 고른다. 발판 사이의 이동은 위험하므로, 보그단은 발판 $i$ 에서 발판 $j$ 로 다음 두 조건을 모두 만족할 때만 이동할 수 있다. 발판 $j$ 가 발판 $i$ 의 내부에 있어야 하고, 발판 $i$ 의 내부에 있으면서 발판 $j$ 를 포함하는 다른 발판 $k$ 가 없어야 한다.

각 발판에서 출발해 그 발판이 아닌 다른 발판에서 끝나는 경로의 수를 보그단이 구하려 한다. 두 경로는 한쪽에는 있고 다른 쪽에는 없는 발판이 하나라도 있으면 서로 다르다.

각 발판에서 출발하는 경로의 수를 세도록 보그단을 도와라. 경로의 수가 매우 클 수 있으므로 $10^9 + 7$ 로 나눈 나머지를 구하라.

입력

첫 줄에 정수 $n$ ( $1 \le n \le 3 \cdot 10^5$ )이 주어진다. 발판의 수이다.

다음 $n$ 개의 줄에는 발판의 정보가 주어진다. $i$ 번째 줄에는 $i$ 번째 선분의 양 끝을 나타내는 두 정수 $l_i$ , $r_i$ ( $1 \le l_i \le r_i \le 10^9$ )가 주어진다.

출력

$n$ 개의 정수를 출력한다. $i$ 번째 정수는 발판 $i$ 에서 출발하는 서로 다른 경로의 수를 $10^9 + 7$ 로 나눈 나머지이다.

예제2

예제 1
입력
```
5
1 5
1 4
1 3
1 2
1 1
```
예상 출력
```
5 4 3 2 1
```
예제 2
입력
```
4
3 3
1 4
1 5
2 5
```
예상 출력
```
1 2 5 2
```