【Algorithm】逆序数的分治求解

逆序数的分治求解，时间复杂度O(nlgn)。基本思想是在归并排序的基础上加逆序计数。
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 using namespace std;
 7 
 8 #define MAXN 100005
 9 
10 int a[MAXN], b[MAXN];
11 int c[MAXN];
12 int ans, n;
13 
14 void merge(int *a, int l, int r) {
15     int mid = (l+r)>>1;
16     int i = l, j = mid+1;
17     int n = 0;
18     
19     while (i<=mid && j<=r) {
20         if (a[i] <= a[j]) {
21             c[n++] = a[i++];
22         } else {
23             c[n++] = a[j++];
24             ans += (mid-i+1);
25         }
26     }
27     while (i <= mid)
28         c[n++] = a[i++];
29     while (j <= r)
30         c[n++] = a[j++];
31     for (i=0, j=l; i<n; ++i, ++j)
32         a[j] = c[i];
33 }
34 
35 void mergeSort(int *a, int l, int r) {
36     int mid = (l+r)>>1;
37     
38     if (l >= r)
39         return ;
40     mergeSort(a, l, mid);
41     mergeSort(a, mid+1, r);
42     merge(a, l, r);
43 }
44 
45 void bruteSolve(int *b, int l, int r) {
46     int i, j;
47     
48     for (i=l; i<=r; ++i) {
49         for (j=l; j<=i; ++j) {
50             if (b[j] > b[i])
51                 ++ans;
52         }
53     }
54 }
55 
56 void init() {
57     int i;
58     
59     n = rand()%(MAXN-1)+1;
60     for (i=1; i<=n; ++i) {
61         a[i] = rand();
62         b[i] = a[i];
63     }
64 }
65 
66 void solve() {
67     clock_t beg, end;
68     int tmp;
69     
70     ans = 0;
71     beg = clock();
72     mergeSort(a, 1, n);
73     end = clock();
74     printf("nlgn: ans  = %d
", ans);
75     printf("      time = %.2lf
", (double)(end-beg)/CLOCKS_PER_SEC);
76     
77     tmp = ans;
78     ans = 0;
79     beg = clock();
80     bruteSolve(b, 1, n);
81     end = clock();
82     printf("n*n : ans  = %d
", ans);
83     printf("      time = %.2lf
", (double)(end-beg)/CLOCKS_PER_SEC);
84     
85     if (tmp != ans)
86         printf("**** wrong ****
");
87     printf("
");
88 }
89 
90 int main() {
91     int t = 30;
92     
93     while (t--) {
94         init();
95         solve();
96     }
97     
98     return 0;
99 }