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\n", ans);75     printf("      time = %.2lf\n", (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\n", ans);83     printf("      time = %.2lf\n", (double)(end-beg)/CLOCKS_PER_SEC);84     85     if (tmp != ans)86         printf("**** wrong ****\n");87     printf("\n");88 }89 90 int main() {91     int t = 30;92     93     while (t--) {94         init();95         solve();96     }97     98     return 0;99 }