!/bin/python3

import math import os import random import re import sys

#

Complete the 'countInversions' function below.

#

The function is expected to return a LONG_INTEGER.

The function accepts INTEGER_ARRAY arr as parameter.

#

def countInversions(arr):

def merge_sort_count(arr):
    if len(arr) <= 1:
        return arr, 0

    mid = len(arr) // 2
    left, left_inv = merge_sort_count(arr[:mid])
    right, right_inv = merge_sort_count(arr[mid:])

    merged, split_inv = merge_count(left, right)
    total_inv = left_inv + right_inv + split_inv
    return merged, total_inv

def merge_count(left, right):
    merged = []
    i = j = 0
    inversions = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            inversions += len(left) - i
            j += 1

    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, inversions

_, total_inversions = merge_sort_count(arr)
return total_inversions

if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

t = int(input().strip())

for t_itr in range(t):
    n = int(input().strip())

    arr = list(map(int, input().rstrip().split()))

    result = countInversions(arr)

    fptr.write(str(result) + '\n')

fptr.close()

include

include

// Merge and count inversions long long mergeAndCount(int arr[], int temp[], int left, int mid, int right) { long long inv_count = 0; int i = left; int j = mid; int k = left;

while (i <= mid - 1 && j <= right) {
    if (arr[i] <= arr[j]) {
        temp[k++] = arr[i++];
    } else {
        temp[k++] = arr[j++];
        inv_count += (mid - i);
    }
}

while (i <= mid - 1)
    temp[k++] = arr[i++];

while (j <= right)
    temp[k++] = arr[j++];

for (i = left; i <= right; i++)
    arr[i] = temp[i];

return inv_count;

}

// Merge sort with inversion count long long mergeSortAndCount(int arr[], int temp[], int left, int right) { long long inv_count = 0; if (left < right) { int mid = (left + right) / 2;

    inv_count += mergeSortAndCount(arr, temp, left, mid);
    inv_count += mergeSortAndCount(arr, temp, mid + 1, right);
    inv_count += mergeAndCount(arr, temp, left, mid + 1, right);
}
return inv_count;

}

int main() { int t; scanf("%d", &t);

while (t--) {
    int n;
    scanf("%d", &n);

    int* arr = (int*)malloc(n * sizeof(int));
    int* temp = (int*)malloc(n * sizeof(int));

    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    long long result = mergeSortAndCount(arr, temp, 0, n - 1);
    printf("%lld\n", result);

    free(arr);
    free(temp);
}

return 0;

}

include

include

using namespace std;

long long mergeAndCount(vector& arr, vector& temp, int left, int mid, int right) {

long long inversion_count = 0;

int i = left;

int j = mid;

int k = left;



while (i <= mid - 1 && j <= right) {

    if (arr[i] <= arr[j]) {

        temp[k++] = arr[i++];

    } else {

        temp[k++] = arr[j++];

        inversion_count += (mid - i);

    }

}



while (i <= mid - 1) {

    temp[k++] = arr[i++];

}



while (j <= right) {

    temp[k++] = arr[j++];

}



for (i = left; i <= right; i++) {

    arr[i] = temp[i];

}



return inversion_count;

}

long long mergeSortAndCount(vector& arr, vector& temp, int left, int right) {

long long inversion_count = 0;

if (left < right) {

    int mid = left + (right - left) / 2;



    inversion_count += mergeSortAndCount(arr, temp, left, mid);

    inversion_count += mergeSortAndCount(arr, temp, mid + 1, right);

    inversion_count += mergeAndCount(arr, temp, left, mid + 1, right);

}

return inversion_count;

}

long long countInversions(vector& arr) {

int n = arr.size();

vector<int> temp(n);

return mergeSortAndCount(arr, temp, 0, n - 1);

}

int main() {

int t;

cin >> t;



while (t--) {

    int n;

    cin >> n;

    vector<int> arr(n);

    for (int i = 0; i < n; i++) {

        cin >> arr[i];

    }

    cout << countInversions(arr) << endl;

}



return 0;

}

Java Solution

    public static long countInversions(List<Integer> arr) {
        int size = arr.size();
        AtomicLong atomicLong = new AtomicLong(0L);
        
        mergeSort(arr, 0, size, atomicLong);
        
        return atomicLong.get();
    }
    
    private static void mergeSort(List<Integer> arr, int firstIndex, int lastIndex, AtomicLong atomicLong){
        if(firstIndex >= lastIndex){
            return;
        }
        final int mediumIndex = firstIndex + ((lastIndex - firstIndex) / 2);
        if(mediumIndex == firstIndex){
            return;
        }
        mergeSort(arr, firstIndex, mediumIndex, atomicLong);
        mergeSort(arr, mediumIndex, lastIndex, atomicLong);
        merge(arr, firstIndex, mediumIndex, lastIndex, atomicLong);
    }
    
    private static void merge(List<Integer> arr, int firstIndex, int mediumIndex, int lastIndex, AtomicLong atomicLong){
        final List<Integer> firstList = arr.subList(firstIndex, mediumIndex).stream().collect(Collectors.toList());
        final List<Integer> secondList = arr.subList(mediumIndex, lastIndex).stream().collect(Collectors.toList());
        
        final int firstSize = firstList.size();
        final int secondSize = secondList.size();
        
        if(firstSize == 0 || secondSize == 0){
            return;
        }
        
        int i = 0, j = 0, k = firstIndex;
        while(i<firstSize && j < secondSize){
            int first = firstList.get(i);
            int second = secondList.get(j);
            if(first <= second){
                arr.set(k, first);
                i++;
            }
            else{
                arr.set(k, second);
                j++;
                atomicLong.addAndGet(firstSize-i);
            }
            k++;
        }
        
        while(i<firstSize){
            arr.set(k, firstList.get(i));
            i++;
            k++;
        }
        
        while(j < secondSize){
            arr.set(k, secondList.get(j));
            j++;
            k++;
        }
    }