思路：利用归并排序，先分解区间。最后合并区间的时候找到逆序的个数。（可以画图来理解归并排序）

代码：

1 #include 
         
           2 #include 
          
            3 using namespace std; 4  5 int a[50005]; 6 int res[50005]; 7 int ans; 8  9 void merge(int l,int r){10     //cout<
           
            <<"  "<
            
             <
             
              >1;12     int i = l,j = mid+1;13     int cur = l;14     while(i <= mid && j <= r){15         if(a[i] <= a[j])16             res[cur++] = a[i++];17         else{18             res[cur++] = a[j++];19             ans += mid-i+1;        //找到逆序的个数20         }21     }22     while(i <= mid)    res[cur++] = a[i++];23     while(j <= r)    res[cur++] = a[j++];24     for(int i = l;i <= r;i ++)    a[i] = res[i];25 }26 void mer_sort(int l,int r){27     if(l < r){28         int mid = (l+r)>>1;29         mer_sort(l,mid);        //分解30         mer_sort(mid+1,r);        //分解31         merge(l,r);                //合并32     }33 }34 int main()35 {36     int n;37     while(cin>>n){38         for(int i = 1;i <= n;i ++)    cin>>a[i];39 40         ans = 0;41         mer_sort(1,n);42         cout<
              
               <