逆序数的分治求解，时间复杂度O(nlgn)。基本思想是在归并排序的基础上加逆序计数。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           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
          
           >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 }