문제

https://www.acmicpc.net/problem/1517


알고리즘

펜윅트리


풀이

$N$제한이 50만이고 배열의 inversion들을 카운트 하는 문제입니다.

버블소트에서의 교환횟수는 inversion의 수와 동일합니다. inversion이란 $i$<$j$ && $A[i]$>$A[j]$ 인 상황을 의미합니다. inversion을 찾으면 swap을 진행하고 inversion의 수가 하나 줄어들고 inversion이 0이 되면 소트가 종료됩니다. 이중포문을 통해 $O(N^2)$에 inversion의 수를 구할 수 있지만 $N$제한이 50만이므로 더 빠른 알고리즘이 필요합니다.

이 문제 와 비슷하다고 생각되어 좌표압축 + 세그먼트 트리로 해결하여 풀었지만 좀더 간단하게 푸는 방법을 설명해드리겠습니다.

inversion을 카운트 하기 위해선 $i$<$j$ && $A[i]$>$A[j]$ 을 만족해야합니다. 이 조건은 $A[i]$>$A[j]$ &&$i$<$j$과 동일함을 알 수 있습니다. 즉 값을 인덱스로 사용하고, 인덱스를 값으로 사용하게 된다면 좌표압축을 진행할 필요없이 인덱스를 펜윅트리에 업데이트하여 사용할 수 있습니다.

유의해야할 점은 주어지는 값들이 모두 동일할 때 입니다. 이 때는 인덱스가 큰 값이 앞에 오게 정렬을 하여 동일한 값(값을 인덱스로 생각하므로 변환후 같은 인덱스)들이 서로를 세지 않도록 주의합시다. 시간복잡도는 $O(NlogN)$입니다.

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

typedef pair<int, int> pii;

vector<pii> arr;
vector<int> fenwick;
int N;

int query(int idx) {
    int ret = 0;
    while (idx) {
        ret += fenwick[idx];
        idx -= idx & -idx;
    }
    return ret;
}

void update(int idx,int val) {
    while (idx <= N) {
        fenwick[idx] += val;
        idx += idx & -idx;
    }
}

int main() {
    FAST;
    cin >> N;
    arr.resize(N);
    fenwick.resize(N + 1);
    rep(i, N) {
        auto& [a, b] = arr[i];
        cin >> a;
        b = i;
    }
    sort(arr.rbegin(), arr.rend());

    long long ans = 0;
    for (auto [a, b] : arr) {
        b += 1;
        ans += query(b - 1);
        update(b,1);
    }
    cout << ans;

    return 0;
}