归并排序求逆序对

　　#include<iostream> 　　#include<algorithm> 　　#include<cstring> 　　using namespace std; 　　const int N=1e5+10; 　　int a[N]; 　　int ans=0; 　　int tmp[N]; 　　void mergesort(int a[],int l,int r) 　　{ 　　if(l>=r)return; 　　int mid=l+r>>1; 　　mergesort(a,l,mid); 　　mergesort(a,mid+1,r); 　　int i=l,j=mid+1; 　　int k=0; 　　while(i<=mid&&j<=r) 　　{ 　　if(a[i]<=a[j]) 　　{ 　　tmp[k++]=a[i++]; 　　} 　　else 　　{ 　　tmp[k++]=a[j++]; 　　ans+=mid-i+1;//与i后面的数均构成逆序，个数mid-i+1 　　} 　　} 　　while(i<=mid)tmp[k++]=a[i++]; 　　while(j<=r)tmp[k++]=a[j++]; 　　for(int i=l,j=0;i<=r;i++,j++)a[i]=tmp[j];   　　} 　　int main() 　　{ 　　int n; 　　cin>>n; 　　for(int i=1;i<=n;i++) 　　{ 　　cin>>a[i]; 　　} 　　mergesort(a,1,n); 　　// for(int i=1;i<=n;i++)cout<<a[i]<<' '; 　　cout<<ans<<endl;   　　return 0;   　　}