超快速排序问题也是该解法

https://www.acwing.com/file_system/file/content/errors/no_permission/

(扩展)星际争霸

import java.util.*;

public class Main {
    static final int N = 100010;
    static int[] a = new int[N], t = new int[N];
    static int n;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = Integer.parseInt(sc.nextLine());
        String[] s = sc.nextLine().split(" ");
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(s[i]);

        long ans = merge_sort(0, n - 1);

        System.out.println(ans);
    }

    static long merge_sort(int l, int r) {
        if (l >= r) return 0;
        int mid = l + r >> 1;

        long res = merge_sort(l, mid) + merge_sort(mid + 1, r);

        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (a[i] <= a[j]) t[k++] = a[i++];
            else {
                t[k++] = a[j++];
                res += mid - i + 1;
            }
        }

        while (i <= mid) t[k++] = a[i++];
        while (j <= r) t[k++] = a[j++];

        for (i = l, j = 0; i <= r; i++, j++) a[i] = t[j];

        return res;
    }
}

树状数组求解逆序对

import java.util.*;

public class Main {
    static final int N = 100010;
    static int[] tr = new int[N];
    static int n;

    static int lowbit(int x) {
        return x & (-x);
    }

    static void add(int x, int v) {
        for (int i = x; i <= n; i += lowbit(i))
            tr[i] += v;
    }

    static long query(int r) {
        long res = 0;
        for (int i = r; i > 0; i -= lowbit(i))
            res += tr[i];
        return res;        
    }

    static int find(int[] unique, int x) {
        return Arrays.binarySearch(unique, x) + 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[] arr = new int[n + 1];
        ArrayList<Integer> alls = new ArrayList<>();

        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
            alls.add(arr[i]);
        }

        int[] unique = alls.stream().distinct().sorted().mapToInt((o1) -> o1).toArray();
        int len = unique.length;

        long ans = 0;
        for (int i = 1; i <= n; i++) {
            /*
                在线段树中顺序添加arr[i], 因此当前的数的个数为query(len)
                要寻找的是逆序对, 对于数arr[i], 就是查看有多少数比arr[i]要大
                比arr[i]小的数的个数为query(idx), 因此对于arr[i]逆序对的数量为
                query(len) - query(idx);累加即可
            */
            int idx = find(unique, arr[i]);
            ans += query(len) - query(idx);
            add(idx, 1); 
        }

        System.out.println(ans);
    }
}