SPOJ 6256. Inversion Count Solution

Problem : SPOJ 6256. Inversion Count

Problem type: Counting Inversion Problem(Merge Sort).
Difficulty : Easy.

Problem Statement :

Let A[0...n - 1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A. Given n and an array A your task is to find the number of inversions of A.

Input

The first line contains t, the number of testcases followed by a blank space. Each of the t tests start with a number n (n <= 200000). Then n + 1 lines follow. In the ith line a number A[i - 1] is given (A[i - 1] <= 10^7). The (n + 1)th line is a blank space.

Output

For every test output one line giving the number of inversions of A.

Example

Input:

2

3
3
1
2

5
2
3
8
6
1

Output: 

2
5

Solution:

 C implementation of this problem.

#include <stdio.h>  

#define sz 500000  
#define inf 1000000000  
long a[sz+2],L[sz+2],R[sz+2];  
long long cnt;

void merge(long p,long q,long r){  
 long i,j,k,ind1,ind2;  

 for(i = p,ind1 = 1;i <= q;i++){  
  L[ind1++] = a[i];  
 }  
 L[ind1] = inf;  

 for(i = q+1,ind2 = 1;i <= r;i++){  
  R[ind2++] = a[i];  
 }  
 R[ind2] = inf;  

 i = j = 1;  

 for(k = p;k <= r;k++){  
  if(L[i] > R[j]){  
   cnt += ind1 - i;  
   a[k] = R[j];  
   j++;  
  }  
  else{  
   a[k] = L[i];  
   i++;  
  }  
 }  
}  

void mergeSort(long p,long r){  
 if(p < r){  
  long q = (p+r)/2;  
  mergeSort(p,q);  
  mergeSort(q+1,r);  
  merge(p,q,r);  
 }  
}  

int main(){  
 long i,n,t;

 scanf("%ld",&t);
 while( t-- ){ 
  scanf("%ld",&n);
  for(i = 1;i <= n; i++){  
   scanf("%ld",&a[i]);  
  }  
  cnt = 0;  
  mergeSort(1,n);  
  printf("%lld\n",cnt);  
 }  

 return 0;  
}