AcWing逆序对的数量(Java)

给定一个长度为?n?的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第?i?个和第?j?个元素，如果满足?i<j?且?a[i]>a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数?n，表示数列的长度。

第二行包含?n?个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1≤n≤100000，
数列中的元素的取值范围 [1,10^9]。

输入样例：

6
2 3 4 5 6 1

输出样例：

5

import java.util.Scanner;

public class Main {
    static int[] q,stm;
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int len=scan.nextInt();
        q=new int[len];
        stm=new int[len];
        long ans=0;
        for(int i=0;i<len;i++){
            q[i]=scan.nextInt();
        }
        ans=msort(0,len-1);
        System.out.println(ans);
    }
    public static long msort(int l,int r){
        if(l>=r){
            return 0;
        }
        int mid=l+(r-l)/2;
        long res=msort(l,mid)+msort(mid+1,r);
        int k=0,i=l,j=mid+1;
        while(i<=mid&&j<=r){
            if(q[i]<=q[j]){
                stm[k]=q[i];
                k++;
                i++;
            }
            else{
                stm[k]=q[j];
                k++;
                j++;
                res+=mid-i+1;
            }
        }
        while(i<=mid){
            stm[k]=q[i];
            k++;
            i++;
        }
        while(j<=r){
            stm[k]=q[j];
            k++;
            j++;
        }
        for(int ki=l,kj=0;ki<=r;ki++,kj++){
            q[ki]=stm[kj];
        }
        return res;
    }
}