用暴力会超时,所以选择归并排序
static int N=1000010;
public static void main(String[] args) {
int []arr=new int[N];
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for (int i = 0; i < n; i++) {
arr[i]=sc.nextInt();
}
System.out.println(merge_sort(arr, 0, n - 1));
}
private static long merge_sort(int[] arr, int l, int r) {
if(l>=r) return 0;
int mid=l+r>>1;
long result=0;
int []s=new int[r-l+1];
result=merge_sort(arr,l,mid)+merge_sort(arr,mid+1,r);
int i=l,j=mid+1,k=0;
while (i<=mid &&j<=r){
if(arr[i]<=arr[j]) s[k++]=arr[i++];
else{
s[k++]=arr[j++];
result+=mid-i+1;
}
}
while (i<=mid) s[k++]=arr[i++];
while (j<=r) s[k++]=arr[j++];
for (i = l, k = 0; i <= r; i++, k++) {
arr[i] = s[k];
}
return result;
}