HW3C

#include <iostream>
#include <vector>

using namespace std;

long int merge(vector <int> & A, int low, int high) {

    int mid = (low + high) / 2;

    int Al_size = mid - low + 1;
    vector <int> Al(Al_size);
    for (int i = 0; i < Al_size; i++) {
        Al[i] = A[i + low];
    }

    int Ar_size = high - mid;
    vector <int> Ar(Ar_size);
    for (int i = 0; i < Ar_size; i++) {
        Ar[i] = A[i + mid + 1];
    }

    int i = 0, j = 0, k;
    long int count = 0;
    for (k = low; k <= high; ) {
        if (Al[i] <= Ar[j]) {
            A[k] = Al[i];
            i++;
            k++;
            if (i >= Al_size)   break;
        }
        else {
            A[k] = Ar[j];
            k++;
            j++;
            count += Al_size - i;
            if (j >= Ar_size)  break;
        }
    }

    while (i < Al_size) {
        A[k] = Al[i];
        k++;
        i++;
    }

    while (j < Ar_size) {
        A[k] = Ar[j];
        k++;
        j++;
    }

    return count;
}

long int Inversion (vector <int> & A, int low, int high) {
    long int count = 0;
    if (low < high) {

        int mid = (low + high) / 2;

        count += Inversion(A, low, mid);
        count += Inversion(A, mid + 1, high);

        count += merge(A, low, high);
    }
    return count;
}

int main() {
    int N;
    cin >> N;
    vector <int> A (N);

    for (int i = 0; i < N; i++)
        cin >> A[i];

    long int count = Inversion(A, 0, N - 1);
    cout << count;

    return 0;
}