求逆序数_归并排序

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 #define maxxx 1000005
 5 
 6 using namespace std;
 7 
 8 long int a[maxxx],b[maxxx];//b作临时数组
 9 long long int cou;
10 
11 void mergee(long int a[],int start,int mid,int endd){
12     int i=start,j=mid+1;
13     int k=start;
14     while(i<=mid&&j<=endd){
15         if(a[i]<=a[j]){
16             b[k++]=a[i++];
17         }else{
18             cou+=j-k;
19             b[k++]=a[j++];
20         }
21     }
22     while(i<=mid){
23         b[k++]=a[i++];
24     }
25     while(j<=endd){
26         b[k++]=a[j++];
27     }
28     for(int i=start;i<=endd;i++){
29         a[i]=b[i];
30     }
31 }
32 
33 void mergesort(long int a[],int start,int endd){
34     if(start<endd){
35         int mid=(start+endd)/2;
36         mergesort(a,start,mid);
37         mergesort(a,mid+1,endd);
38         mergee(a,start,mid,endd);
39     }
40 }
41 
42 int main()
43 {
44     int t;
45     int n;
46     scanf("%d",&t);
47     for(int j=0;j<t;j++){
48         cou=0;
49         scanf("%d",&n);
50             for(int i=0;i<n;i++){
51             scanf("%d",a+i);
52         }
53         mergesort(a,0,n-1);
54         printf("%lld\n",cou);
55     }
56     return 0;
57 }