문제

• 
• 시간 제한: 1초
• 메모리 제한: 512MB

Problem Analysis

A[i]보다 작은 값이 A[i+1, ...., N-1] 중에 k 개가 있다면 k 번 swap 해야 한다. 각 i 별로 K를 모두 구해 합해주면 된다. 이때, 매번 Naive 하게 수를 비교하면 O(N^2)이 된다. 대신에, Segment Tree로 각 범위의 존재하는 수의 개수를 구하면 더 빠를 것이다.

Algorithm

1. 범위를 압축한다.
2. N-1부터 시작하여 0까지 반복한다.
   • Segment Tree에서 A[i]보다 작은 범위의 개수를 구한다
   • A[i] 값을 하나 SegTree에 추가한다

Data Structure

• ST[]: segment Tree
• 범위 압축 Array

결과

Other

시간 복잡도는 O(NlogN)이다.
문제 설명에 Divide and Conquer 방식으로도 풀 수 있다고 한다.