1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
|
#include<iostream>
using namespace std;
long long int mergearr(int arr[],int l,int m,int r)
{
long long int inv=0;
int n1=m-l+1;
int n2=r-m;
int left[n1],right[n2];
for(int i=l;i<=m;i++)
left[i-l]=arr[i];
for(int i=m+1;i<=r;i++)
right[i-m-1]=arr[i];
int i=0,j=0,k=l;
while(i<n1 && j<n2)
{
if(left[i]<=right[j])
{
arr[k]=left[i];
i++;
k++;
}
else
{
arr[k]=right[j];
inv+=m-i;
k++;
j++;
}
}
while(i<n1)
{
arr[k]=left[i];
k++;
i++;
}
while(j<n2)
{
arr[k]=right[j];
k++;
j++;
}
return inv;
}
long long int mergesort(int arr[],int l,int r)
{
long long int inv=0;
if(l>=r)
return inv;
int m=(l+r)/2;
inv+=mergesort(arr,l,m);
inv+=mergesort(arr,m+1,r);
inv+=mergearr(arr,l,m,r);
return inv;
}
int main()
{
int test;
cin>>test;
cin.ignore();
while(test>0)
{
int n;
string blank;
getline(cin,blank);
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
int inv=mergesort(arr,0,n-1);
cout<<inv<<endl;
test--;
}
return 0;
}
|