JAVA 代码

import java.util.Scanner;
import java.io.BufferedInputStream;

public class Main {
    //程序入口
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        System.out.print(Count(arr, 0, n-1));

    }
    private static long res = 0;
    private static long Count(int[] arr, int l, int r){

        if(l >= r)
            return res;
        //0. 确定分界点---取中点
        int mid = l + r >> 1;
        //1. 递归排序左边和右边
        Count(arr, l, mid);
        Count(arr, mid + 1, r);
        //2. 归并---将两个有序数组合并成一个有序数组---双指针算法
        //对两个数组分别取头指针，不断比较两个指针大小，在开辟一个新数组容纳
        int[] temp = new int[r - l + 1];
        int k = 0;//表示当前temp一共有多少个数
        int i = l,j = mid + 1 ;//两个指针
        while(i <= mid && j <= r){
            if(arr[i] <= arr[j])
                temp[k++] = arr[i++];
            else{
                res += mid - i + 1;
                temp[k++] = arr[j++];

            }

        }
        while(i <= mid)
            temp[k++] = arr[i++];
        while(j <= r)
            temp[k++] = arr[j++];
        for (i = l, j = 0; i <= r; i++, j++)
            arr[i] = temp[j];
        return res;

    }
}