1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 long long int a[1000001]; 5 int tot; 6 int n; 7 long long int ans[1000001];//储存结果  8 int now;//表示已经有多少个结果  9 void f(int s,int t)10 {11     //int mid,i,j,k;12     if(s==t)return;13     int mid=(s+t)/2;14     f(s,mid);15     f(mid+1,t);16     int i=s;17     int j=mid+1;18     now=s;19     while(i<=mid&&j<=t)20     {21         if(a[i]<=a[j])22         {23             //tot++;24         25             ans[now]=a[i];26             i++;27             now++;28         }29         else30         {    31             tot=tot+j-i;32             ans[now]=a[j];33             j++;34             now++;35         }36     }37     while(i<=mid)38     {39         ans[now]=a[i];40         i++;41         now++;42     }43     while(j<=t)44     {45         ans[now]=a[j];46         j++;47         now++;48     }49     for (i=s;i<=t;i++)//把合并后的有序数据重新放回a数组50         a[i] = ans[i];51 52 }53 int main()54 {55     int n;56     cin>>n;57     for(int i=1;i<=n;i++)58         cin>>a[i];59     f(1,n);60     //cout<<tot;61     /*for(int i=1;i<=n;i++)62     {63         cout<<a[i]<<" ";64     }*/65     cout<<tot;66     return 0;67 }