BOJ 10090번 Counting Inversions

BOJ : https://www.acmicpc.net/problem/10090

github : https://github.com/junho0956/Algorithm/blob/master/10090/10090/%EC%86%8C%EC%8A%A4.cpp

 

도치수는 merge_sort 를 이용한 분할정복으로 해결할 수 있습니다.

 

#include <iostream>
using namespace std;
 
#define MAX 1000000
 
int arr[MAX];
int dup[MAX];
 
long long partition(int s, int m, int e) {
    int left = s, right = m + 1;
    int index = 0;
    long long result = 0;
    while (left <= m && right <= e) {
        if (arr[right] >= arr[left]) {
            dup[index++] = arr[left++];
        }
        else {
            result += m - left + 1;
            dup[index++] = arr[right++];
        }
    }
 
    while (left <= m) dup[index++] = arr[left++];
    while (right <= e) dup[index++] = arr[right++];
 
    for (int i = 0; i <= e - s; i++) {
        arr[s + i] = dup[i];
    }
 
    return result;
}
 
long long merge_sort(int s, int e) {
    long long result = 0;
    if (s < e) {
        int pivot = (s + e) / 2;
        result += merge_sort(s, pivot);
        result += merge_sort(pivot + 1, e);
        result += partition(s, pivot, e);
    }
    return result;
}
 
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N; cin >> N;
 
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    long long result = merge_sort(0, N - 1);
 
    cout << result;
    return 0;
}