6004 : 분할정복 — 합병 정렬
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
합병 정렬(Merge Sort)을 재귀 함수로 구현하여 배열을 오름차순으로 정렬하십시오.
동시에, 정렬되기 전의 원래 배열에서 역전쌍(Inversion Count)의 총 개수를 $10^9+7$로 나눈 나머지를 구하십시오.
역전쌍이란 $i < j$ 이면서 $arr[i] > arr[j]$ 인 인덱스 쌍 $(i, j)$를 말합니다.
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 10^6$ (정수)
• 배열 원소: $-10^9 \le a_i \le 10^9$ (정수)
• 역전쌍 수는 $10^9 + 7$로 나눈 나머지를 출력합니다.
동시에, 정렬되기 전의 원래 배열에서 역전쌍(Inversion Count)의 총 개수를 $10^9+7$로 나눈 나머지를 구하십시오.
역전쌍이란 $i < j$ 이면서 $arr[i] > arr[j]$ 인 인덱스 쌍 $(i, j)$를 말합니다.
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 10^6$ (정수)
• 배열 원소: $-10^9 \le a_i \le 10^9$ (정수)
• 역전쌍 수는 $10^9 + 7$로 나눈 나머지를 출력합니다.
입력 설명
첫째 줄에 정수 $N$이 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
[제약 조건]
• $1 \le N \le 500{,}000$
• 각 원소는 $-10^9$ 이상 $10^9$ 이하의 정수
출력 설명
첫째 줄에 오름차순으로 정렬된 $N$개의 정수를 공백으로 구분하여 출력합니다.
둘째 줄에 역전쌍(Inversion Count)의 총 개수를 $10^9+7$로 나눈 나머지를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
5 4 3 2 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 2 3 4 5
10도움
합병 정렬(Merge Sort)의 병합(Merge) 단계에서 오른쪽 원소가 선택될 때 왼쪽 배열의 남은 원소 수를 누적합니다.