AcWing 788. 逆序对的数量

活动 - AcWing

 

【归并排序】归并排序的经典应用，按照元素从大到小的顺序进行归并排序，如果前半部分有个元素比后半部分大，则后半部分从这个元素开始一直到r都能和前面的元素构成逆序对。

// package AcWing.course;
import java.io.StreamTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {

    // 9:14. 9:22
    static int n;
    static int[] arr, tmp;
    static StreamTokenizer st;
    static long ans = 0;

    static int nextInt() throws Exception {
        st.nextToken();
        return (int)st.nval;
    }

    static void mergeSort(int l, int r){
        if(l >= r) return;
        int mid = (l + r) >>> 1;
        mergeSort(l, mid); mergeSort(mid + 1, r);
        int i = l, j = mid + 1, k = 0;
        while(i <= mid && j <= r){
            if(arr[i] > arr[j]){
                ans += r - j + 1;
                tmp[k++] = arr[i++];
            }else{
                tmp[k++] = arr[j++];
            }
        }
        while(i <= mid) tmp[k++] = arr[i++];
        while(j <= r) tmp[k++] = arr[j++];
        for(i = l, j = 0; j < k; i++, j++) arr[i] = tmp[j];
    }

    public static void main(String[] args) throws Exception {
        st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter pw = new PrintWriter(System.out);
        n = nextInt();
        arr = new int[n];
        tmp = new int[n];
        for(var i = 0; i < n; i++) arr[i] = nextInt();
        mergeSort(0, n - 1);
        pw.println(ans);
        pw.flush();
    }

}