九度oj 1348 数组中的逆序对

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cstdio>
 6 typedef unsigned long long ull;
 7 const int Max_N = 100010;
 8 ull res;
 9 int arr[Max_N], temp[Max_N];
10 void Merge(int *A, int l, int m, int r) {
11     int p = 0;
12     int x = l, y = m + 1;
13     while (x <= m && y <= r) {
14         if (A[x] > A[y]) res += m - x + 1, temp[p++] = A[y++];
15         else temp[p++] = A[x++];
16     }
17     while (x <= m) temp[p++] = A[x++];
18     while (y <= r) temp[p++] = A[y++];
19     for (x = 0; x < p; x++) A[l + x] = temp[x];
20 }
21 void MergeSort(int *A, int l, int r) {
22     int mid;
23     if (l < r) {
24         mid = (l + r) >> 1;
25         MergeSort(A, l, mid);
26         MergeSort(A, mid + 1, r);
27         Merge(A, l, mid, r);
28     }
29 }
30 int main() {
31 #ifdef LOCAL
32     freopen("in.txt", "r", stdin);
33     freopen("out.txt", "w+", stdout);
34 #endif
35     int n;
36     while (~scanf("%d", &n)) {
37         res = 0;
38         for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
39         MergeSort(arr, 0, n - 1);
40         printf("%lld\n", res);
41     }
42     return 0;
43 }