구간 셔플

시간 제한1초메모리 제한256 MB

요약

배열과 m개의 구간이 주어질 때, 각 구간에서 원소 하나를 1 증가시키거나 구간을 임의로 재배열할 수 있으며, 각 위치 k에 대해 가능한 A_k의 최댓값을 구합니다.

난이도: 어려움10점 중 9점
유형: 그리디, 정렬, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

카나데에게 길이 $n$ 의 수열 $A_{1...n}$ 과, 1부터 $n$ 까지의 인덱스로 이루어진 $m$ 개의 구간 $[L_i, R_i]$ 가 있다. 양 끝 인덱스는 구간에 포함된다. 카나데는 구간마다 하나씩, 총 $m$ 번의 연산을 순서대로 수행한다. $i$ 번째 연산에서 카나데는 다음 두 동작 중 하나를 골라 수행할 수 있다.

$x \in [L_i, R_i]$ 를 골라 $A_x := A_x + 1$ 로 바꾼다.
$A_{L_i...R_i}$ 를 카나데가 원하는 순서로 재배열한다.

모든 연산을 마친 뒤 $A_k$ 의 최댓값을 구하라. 각 $k \in [1, n]$ 에 대해 답을 구하라.

입력

첫 줄에 수열의 길이와 연산 횟수를 나타내는 두 정수 $n$ 과 $m$ 이 주어진다 ( $1 \leq n, m \leq 2 \cdot 10^5$ ). 둘째 줄에는 초기 수열 $A_1, \ldots, A_n$ 이 주어진다 ( $0 \leq A_i \leq 2 \cdot 10^5$ ).

이어서 $m$ 개의 줄에 $i$ 번째 연산의 구간을 나타내는 두 정수 $L_i$ 와 $R_i$ 가 주어진다 ( $1 \leq L_i \leq R_i \leq n$ ).

출력

$n$ 개의 정수를 출력한다. $i$ 번째 정수는 $m$ 번의 연산 후 $A_i$ 가 가질 수 있는 최댓값이다.

예제1

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