1517번: 버블 소트

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


$O(n\lg n)$

버블 정렬시 swap 이 일어나는 경우는 i<j 일때 a[i]>a[j]인 경우이다.
이 개수는 bit를 이용해 쉽게 구할 수 있다.

#include<cstdio>
#include<algorithm>
int n, idx, cnt, bit[500001];
long long r, a[500000];
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i<n; i++) scanf("%d", a + i), a[i] = a[i] * n + i;
    std::sort(a, a + n);
    for (int i = 0; i<n; i++) {
        for (int j = a[i] % n + 1; j <= n; j += j&-j) r += bit[j];
        for (int j = a[i] % n + 1; j; j -= j&-j) bit[j]++;
    }
    printf("%lld", r);
    return 0;
}