1 #include <iostream> 2 #include <queue> 3 #include <climits> 4 #include <algorithm> 5 #include <memory.h> 6 #include <stdio.h> 7 #include <ostream> 8 #include <vector> 9 #include <list>10 #include <cmath>11 #include <string>12 #include <stdexcept>13 #include <stack>14 #include <map>15 using namespace std;16 17 vector<int> a;18 vector<int> tmpa;19 int ans;20 void mergeArray(int l,int mid,int r)21 {22     int i = l;23     int j = mid+1;24     int k = l;25     while(i <= mid && j <=r)26     {27         if(a[i] > a[j])28         {29             tmpa[k++] = a[j++];30             ans += mid-i+1;31         }32         else33         {34             tmpa[k++] = a[i++];35         }36     }37     while(i <= mid)38         tmpa[k++] = a[i++];39     while(j <= r)40         tmpa[k++] = a[j++];41     for(i = l;i<=r;++i)42         a[i] = tmpa[i];43 }44 void merge_sort(int l,int r)45 {46     if(l<r)47     {48         int mid = (l+r)/2;49         merge_sort(l,mid);50         merge_sort(mid+1,r);51         mergeArray(l,mid,r);52     }53 }54 55 int main()56 {57     ans = 0;58     int n;59     cin>>n;60     for(int i = 0 ; i < n ; ++i)61     {62         int tmp;63         cin>>tmp;64         a.push_back(tmp);65         tmpa.push_back(tmp);66     }67     merge_sort(0,n-1);68     cout<<ans<<endl;69     return 0;70 }