1237：求排列的逆序数

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 const int N=1e5+5;
 6 int a[N];
 7 long long ans;
 8 //归并排序
 9 void mergeSort(int begin,int end){
10     //递归终止条件
11     if(begin==end)return;
12 
13     int mid=(begin+end)/2,t[N];
14     mergeSort(begin,mid);
15     mergeSort(mid+1,end);
16     int x=begin,y=mid+1,r=begin;
17     while(x<=mid&&y<=end){
18         if(a[x]>a[y]){
19             //核心算法
20             ans+=mid-x+1;
21             t[r++]=a[y++];
22         }else{
23             t[r++]=a[x++];
24         }
25     }
26     while(x<=mid){
27         t[r++]=a[x++];
28     }
29     while(y<=end){
30         t[r++]=a[y++];
31     }
32     //复制数组
33     while(--r>=begin){
34         a[r]=t[r];
35     }
36 }
37 int main(){
38     cin>>a[0];
39     for(int i=1;i<=a[0];i++)cin>>a[i];
40     mergeSort(1,a[0]);
41     cout<<ans;
42     return 0;
43 }