길이 \(N\)의 정수 수열 \(a_1, a_2, \dots, a_N\) 이 주어진다. 이 수열을 오름차순으로 정렬하기 위해 버블 정렬을 수행할 때, 인접한 두 원소를 서로 바꾸는 연산이 몇 번 일어나는지 구하여라.

이 값은 곧 수열의 반전(inversion)의 개수, 즉 \(i < j\) 이면서 \(a_i > a_j\) 인 순서쌍 \((i, j)\)의 개수와 같다. \(N\)이 크므로 모든 쌍을 직접 세는 \(O(N^2)\) 방법으로는 시간 안에 풀 수 없다.

\(1 \le N \le 200{,}000\)

\(1 \le a_i \le 10^9\)

첫째 줄에 수열의 길이 \(N\)이 주어진다.

둘째 줄에 \(N\)개의 정수 \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\))이 주어진다.

반전의 개수(버블 정렬에서 일어나는 인접 교환 횟수)를 출력한다.

riseoj 작성

출처 Original