import java.util.*;
import java.lang.*;
// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {
    public static int res = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            res = 0;
            int N = in.nextInt();
            int[] arr = new int[N];
            for(int i=0;i<N;i++) arr[i]=in.nextInt();
            mergeSort(arr);
            System.out.println(res);
        }
    }

    public static void mergeSort(int[] arr){
        if(arr.length>1){
            int mid = arr.length/2;
            int[] left = Arrays.copyOfRange(arr,0,mid);
            int[] right = Arrays.copyOfRange(arr,mid,arr.length);
            mergeSort(left);
            mergeSort(right);
            merge(arr,left,right);
        }
    }

    public static void merge(int[] arr, int[] left, int[] right){
        int i=0,j=0,k=0;
        while(i<left.length && j<right.length){
            if(left[i]<=right[j]) arr[k++] = left[i++];
            else {
                arr[k++] = right[j++];
                res+=left.length-i;
            }
        }

        while(i<left.length) arr[k++] = left[i++];
        while(j<right.length) arr[k++] = right[j++]; 
    }
}

官方題解已經(jīng)有歸并排序的主思路了，我看了這個題目的題解非常少，其實更加關(guān)鍵的問題在于：歸并排序中，怎么統(tǒng)計交換了多少次？在哪里加代碼？

我這里給出解答：在歸并排序中，兩個有序數(shù)組進行merge的時候，且發(fā)生了左邊的元素比右邊大的情況，例如：左數(shù)組為[3,4]，右數(shù)組為[1,2]，他們合并的時候，1和2就需要跑到3和4的前面去，這其實就是相當(dāng)于1和3、4交換了2次，2再和3、4交換了2次，最終形成[1,2,3,4]。除了明確維護交換次數(shù)的時機以外，還需要明確具體交換了幾次，那肯定是左邊數(shù)組left剩下多少元素就交換多少次（left.length-i，其中i代表左邊數(shù)組已經(jīng)用過的次數(shù)，例如left = [1,3,4], right = [2]，那么2其實只需要越過3、4就能到達它該呆著的地方，1在2之前就已經(jīng)用過了）