역전 카운팅

뒤집힌 쌍(inversion)의 수를 병합 정렬·펜윅 트리로 O(N log N)에 센다.

플래티넘 V

1강 역전 쌍 세기: 병합 정렬의 부수입 공식

문제 정의

수열 $$A$$ 에서 $$i < j$$ 인데 $$A_i > A_j$$ 인 쌍 $$(i, j)$$ 를 역전(inversion)
이라고 합니다. 역전의 개수는 "수열이 정렬에서 얼마나 먼가"의 척도이며 —
버블 정렬의 교환 횟수와 정확히 같습니다.

나이브하게는 모든 쌍을 보는 $$O(N^2)$$ . 두 가지 표준 도구로 $O(N \log N)$ 에
셀 수 있습니다.

방법 1 — 병합 정렬

병합 정렬의 merge 단계에서 오른쪽 절반의 원소가 왼쪽 절반의 원소보다
먼저 뽑히는 순간, 왼쪽에 남아 있는 원소 수만큼의 역전이 한 번에
발견됩니다.

$\text{count}(A) = \text{count}(L) + \text{count}(R) + \text{merge에서 발견한 교차 역전}$

분할 정복의 전형 — 왼쪽 안, 오른쪽 안, 그리고 경계를 가로지르는 것을
merge가 책임집니다.

방법 2 — 펜윅 트리 (BIT)

수열을 뒤에서 앞으로 훑으며, "지금 원소보다 작은 값이 이미 몇 개
나왔나"를 펜윅 트리로 묻습니다.

값을 좌표 압축한다 (값 범위가 클 때).
$i = N \dots 1$ 순서로: ans += query(A[i] - 1) 후 update(A[i], +1).

값이 같은 쌍은 역전이 아니므로 A[i] - 1까지만 세는 것에 주의.

두 방법의 비교

	병합 정렬	펜윅 트리
시간	$O(N \log N)$	$O(N \log N)$
추가 지식	분할 정복	BIT + 좌표 압축
확장성	"K 이하 차이 쌍" 등 변형에 유연	온라인/부분 질의로 확장 쉬움

어디서 만나는가

두 줄 사이의 전선 교차 수 — 한쪽 순서로 재배열한 뒤 역전 카운팅.
순열의 패리티(짝/홀) 판정, 15-퍼즐 해결 가능성.
"내 앞에 있는 더 큰 수의 개수" 류의 카운팅 전반.

답이 최대 $\binom{N}{2} \approx N^2/2$ 이므로 $$N > 65536$$ 이면 64비트
정수가 필수입니다.

2강 역전 카운팅 구현 두 가지 공식

병합 정렬 버전 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> a, tmp;

ll solve(int lo, int hi) {  // [lo, hi)
    if (hi - lo <= 1) return 0;
    int mid = (lo + hi) / 2;
    ll cnt = solve(lo, mid) + solve(mid, hi);
    int i = lo, j = mid, k = lo;
    while (i < mid || j < hi) {
        if (j == hi || (i < mid && a[i] <= a[j])) {
            tmp[k++] = a[i++];
        } else {
            cnt += mid - i;     // 왼쪽에 남은 모두와 역전
            tmp[k++] = a[j++];
        }
    }
    copy(tmp.begin() + lo, tmp.begin() + hi, a.begin() + lo);
    return cnt;
}

int main() {
    int n;
    cin >> n;
    a.resize(n); tmp.resize(n);
    for (auto &x : a) cin >> x;
    cout << solve(0, n) << '\n';
}

a[i] <= a[j]의 등호가 중요합니다 — 같은 값을 역전으로 세지 않으려면
왼쪽을 먼저 뽑아야 합니다.

펜윅 트리 버전 (Python)

import sys

input = sys.stdin.readline
n = int(input())
a = [int(input()) for _ in range(n)]

# 좌표 압축: 값 → 1..m
sorted_vals = sorted(set(a))
rank = {v: i + 1 for i, v in enumerate(sorted_vals)}
m = len(sorted_vals)

tree = [0] * (m + 1)

def update(i):
    while i <= m:
        tree[i] += 1
        i += i & (-i)

def query(i):  # 1..i 합
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & (-i)
    return s

ans = 0
for x in reversed(a):
    r = rank[x]
    ans += query(r - 1)   # 이미 나온, 나보다 작은 값들
    update(r)
print(ans)

자주 하는 실수

오버플로 — 역전 수는 $$N(N-1)/2$$ 까지 자랍니다. C++은 long long.
같은 값 처리 — merge의 <=, BIT의 query(r - 1). 둘 다 등호를
잘못 두면 같은 값 쌍이 역전으로 집계됩니다.
병합 버전에서 tmp를 재귀마다 새로 만들면 $O(N \log N)$ 메모리 — 전역
버퍼 하나를 재사용하세요.

연습 포인트

같은 문제를 두 방법으로 모두 풀어 보세요. 그다음 "버블 소트 교환 횟수",
"전선 교차" 같은 변형으로 모델링 연습을 하면 좋습니다.