BIT를 이용한 역전쌍

역순쌍은 a[i] > a[j]를 만족하는 i < j인 쌍입니다. 순서가 뒤바뀐 하나의 쌍이며, 배열이 얼마나 정렬되지 않았는지를 측정합니다.

역순쌍의 개수는 버블 sort가 수행할 교환 횟수와 같습니다. 대회 문제에서는 이를 순위나 뒤섞임에 관한 질문 속에 숨겨 두기도 합니다.

모든 쌍을 확인하면 O(n^2)입니다. n이 약 100000이면 100억 번을 확인해야 하므로 시간 제한을 훨씬 넘습니다. 더 영리한 방법이 필요합니다. 🐢

왼쪽에서 오른쪽으로 훑으며 현재 원소보다 앞에 있는 원소 중 더 큰 원소가 몇 개인지 묻습니다. 펜윅 트리가 이 값을 진행하면서 계산해 줍니다.

BIT는 값 전체에 대한 빈도 표를 저장합니다. 갱신(v, 1)은 지금까지 훑은 부분에 값 v가 등장했다는 사실을 기록합니다.

v보다 큰 앞쪽 값의 개수는 지금까지 본 원소 수에서 v 이하의 원소 수를 뺀 값입니다. i번째 원소에서는 i - 질의(v)로 계산합니다.

값이 크거나 음수라면 먼저 순위 1..n으로 매핑하십시오. 이 압축은 순서를 바꾸지 않으면서 BIT의 크기를 작게 유지합니다.

배열을 순회하면서 각 원소보다 큰 값의 개수를 전체 합에 더한 다음 현재 값을 삽입합니다. 실행 중인 전체 합이 역순쌍의 개수가 됩니다.

각 원소마다 질의 한 번과 갱신 한 번을 수행하며, 둘 다 O(log n)입니다. 따라서 전체 계산은 O(n log n) 시간에 끝납니다. 🚀

병합 sort도 병합 단계에서 O(n log n)에 역순쌍을 셉니다. BIT를 사용하는 방법은 시간에 쫓길 때 작성하기 더 짧은 경우가 많습니다.

역순쌍의 개수는 n²/2 정도까지 커질 수 있어 매우 큽니다. 파이썬의 정수는 제한이 없지만, 다른 언어에서는 64비트 자료형이 필요합니다.

훑기에 필요한 비용을 제대로 이해했는지 확인해 보십시오.

왼쪽에서 오른쪽으로 훑으면서 BIT에 앞에 나온 더 큰 값이 몇 개인지 물어 O(n log n)에 역순쌍을 셌습니다. 필요할 때는 값을 압축하십시오. ✅