利用归并排序求逆序对数

                ans+=m-p;

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn=100005;
 4 int n;
 5 int a[maxn];
 6 long long ans=0;
 7 int t[maxn];
 8 void count(int* A,int x,int y)
 9 {
10     if(x+1<y)
11     {
12         int m=(x+y)/2;
13         count(A,x,m);
14         count(A,m,y);
15         int p=x,q=m;
16         int i=x;
17         while(p<m||q<y)
18         {
19             if(q>=y||(p<m&&A[p]<=A[q]))
20             t[i++]=A[p++];
21             else
22             {
23                 t[i++]=A[q++];
24                 ans+=m-p;
25             }
26         }
27               for(int i=x;i<y;i++) A[i]=t[i];
28     }
29 }
30 int main()
31 {
32     cin>>n;
33     for(int i=0;i<n;i++) cin>>a[i];
34     count(a,0,n);
35     cout<<ans<<endl;
36     return 0;
37 }