题目描述
blablabla
样例
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n], memo = new int[n];
for(int i = 0; i < n; i++){
arr[i] = sc.nextInt();
}
System.out.println(mergeSort(arr, 0, n - 1, memo));
}
private static long mergeSort(int[] arr, int l, int r, int[] memo) {
if (l >= r) return 0;
int mid = (l + r) >>> 1;
long ans = 0;
ans += mergeSort(arr, l, mid, memo) + mergeSort(arr, mid + 1, r, memo);
int i = l, j = mid + 1, k = 0;
while (i <= mid) {
while (j <= r && arr[i] > arr[j]) {
ans += mid - i + 1;
memo[k++] = arr[j++];
}
memo[k++] = arr[i++];
}
while (j <= r) memo[k++] = arr[j++];
System.arraycopy(memo, 0, arr, l, r - l + 1);
return ans;
}
}