51Nod 1019 逆序数 (归并排序)

 #include <iostream>

 #include <cstring>

 using namespace std;

 const int maxn = ;

 int a[maxn];

 int res[maxn];

 int ans;

 //归并排序

 void merge(int l, int r){

     //cout<<l<<"  "<<r<<endl;

     int mid = (l + r) >> ;

     int i = l, j = mid + ;

     int cur = l;

     while (i <= mid && j <= r){

         if (a[i] <= a[j])

             res[cur++] = a[i++];

         else{

             res[cur++] = a[j++];

             ans += mid - i + ;        //找到逆序的个数

         }

     }

     while (i <= mid)    res[cur++] = a[i++];

     while (j <= r)    res[cur++] = a[j++];

     //排序好后

     for (int i = l; i <= r; i++)    a[i] = res[i];

 }

 void mer_sort(int l, int r){

     if (l < r){

         int mid = (l + r) >> ;

         mer_sort(l, mid);            //分解

         mer_sort(mid + , r);        //分解

         merge(l, r);                //合并

     }

 }

 int main()

 {

     int n;

     while (cin >> n){

         for (int i = ; i <= n; i++)    cin >> a[i];

         ans = ;

         mer_sort(, n);

         cout << ans << endl;

     }

     return ;

 }