AcWing 788. Number of pairs in reverse order

Activities - AcWing

 

【 Merge sort 】 Classic application of merge sort , Merge and sort the elements from large to small , If the first half has an element larger than the second half , Then the second half starts from this element to r Can form reverse order pairs with the previous elements .

// 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();
    }

}