java
一定要用long,不然会溢出
public class Main {
public static void main(String[] args) throws IOException {
InputStreamReader in = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(in);
int num = Integer.parseInt(br.readLine());
int[] arrs = new int[num];
String[] res = br.readLine().split(" ");
for (int i = 0; i < res.length; i++) {
arrs[i] = Integer.parseInt(res[i]);
}
long cnt = merge_sort(arrs, 0, arrs.length - 1);
System.out.print(cnt);
}
public static long merge_sort(int[] nums, int left, int right) {
if (left >= right) return 0;
int mid = (left + right) >> 1;
long res_l = merge_sort(nums, left, mid);
long res_r = merge_sort(nums, mid + 1, right);
int l = left;
int r = mid + 1;
int[] temp = new int[right - left + 1];
int i = 0;
int res = 0;
while (l <= mid && r <= right) {
if (nums[l] <= nums[r]) {
temp[i] = nums[l];
l += 1;
} else {
res += mid - l + 1;
temp[i] = nums[r];
r += 1;
}
i += 1;
}
while (l <= mid) {
temp[i] = nums[l];
i += 1;
l += 1;
}
while (r <= right) {
temp[i] = nums[r];
i += 1;
r += 1;
}
for (int k = 0; k < right - left + 1; k++) {
nums[left + k] = temp[k];
}
return res + res_l + res_r;
}
}