逆序对的数量

算法思想

1. 划分区间
   1. 从中间划分
2. 递归处理子区间
   1. 使两个子区间有序
   2. 同时求解出两个子区间内部的逆序对的数量
3. 合并子区间
   1. 使整个区间有序
   2. 同时求解出横跨两个子区间的逆序对的数量

逆序对有哪几种

算法模板

import java.util.*;

public class Main {
    static int N = 100010;
    static int[] q = new int[N];
    static long count;
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for(int i = 0; i < n; i ++)
        {
            q[i] = in.nextInt();
        }
        mergeSort(q, 0, n - 1);
        System.out.print(count);
    }
    
    static void mergeSort(int[] q, int l, int r)
    {
        if(l >= r) return ;
        
        int mid = l + r >> 1;
        mergeSort(q, l, mid);
        mergeSort(q, mid + 1, r);
        
        int[] t = new int[r - l + 1];
        int k = 0;
        int i = l, j = mid + 1;
        
        while(i <= mid && j <= r)
        {
            if(q[i] <= q[j]) t[k ++] = q[i ++];
            else 
            {
                t[k ++] = q[j ++];
                count += mid - i + 1;
            }
        }
        while(i <= mid)
        {
            t[k ++] = q[i ++];
        }
        while(j <= r)
        {
            t[k ++] = q[j ++];
        }
        
        for(i = l, k = 0; i <= r; i ++, k ++)
            q[i] = t[k];
    }
}

参考资料