AcWing 788. 逆序对的数量(Java)
原题链接
简单
作者:
火球大的脸盆
,
2022-07-06 19:25:58
,
所有人可见
,
阅读 121
import java.io.*;
public class Main {
public static int[] tmp = new int[100010];
public static long mergeSort(int q[], int l, int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
long ans = mergeSort(q, l, mid) + mergeSort(q, mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (q[i] <= q[j]) tmp[k++] = q[i++];
else {
ans += mid - i + 1;
tmp[k++] = q[j++];
}
}
while (i <= mid) tmp[k++] = q[i++];
while (j <= r) tmp[k++] = q[j++];
for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
return ans;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] in = br.readLine().split(" ");
int[] q = new int[n];
for (int i = 0; i < n; i++) {
q[i] = Integer.parseInt(in[i]);
}
long ans = mergeSort(q, 0, n - 1);
System.out.println(ans);
}
}