1517번: 버블 소트

도저히  모르겠어서 다른 분의 플로그를 참조해서 힌트를 얻었다.

세그먼트 트리 또는 머지 소트를 이용해서 푸는 문제였는데

세그먼트 트리는 모르는 관계로 머지 소트로 풀었다.

(머지 소트로 풀이가 가능하다는 것만 떠올리면 어렵지 않은 문제)

#include <iostream>
#include <vector>
 
long long subArr[500010] = { 0 };
long long count = 0;
 
void mergeSort(std::vector<long long> &val, int start, int end) {
    int mid = (start + end) / 2;
    if (mid - start > 1) {
        mergeSort(val, start, mid);
    }
    if (end - mid > 1) {
        mergeSort(val, mid, end);
    }
    int cur = start;
    int i = start;
    int j = mid;
    while (i < mid && j < end) {
        if (val[i] <= val[j] && i < mid) {
            subArr[cur++] = val[i++];
        }
        else if (j < end) {    
            count += j - i - (cur - i);
            subArr[cur++] = val[j++];
        }
    }
    for (int k = i; k < mid; k++) {
        subArr[cur++] = val[i++];
    }
    for (int k = j; k < end; k++) {
        subArr[cur++] = val[j++];
    }
    for (int k = start; k < end; k++) {
        val[k] = subArr[k];
    }
    
}
 
int main(void) {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int len;
    std::cin >> len;
 
    std::vector<long long> val(len);
    for (int i = 0; i < len; i++) {
        std::cin >> val[i];
    }
 
    mergeSort(val, 0, len);
 
    std::cout << count;
    return 0;
}