INVCNT(Inversion Count) spoj problem solution

HII GUYS.......
this is the our task:

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

method-1(Brute Force)

int count=0;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(a[j]<a[i])
count++;

then print count

BUT::here it lead to TLE bcoz this approach is o(n^2) here n is 200000

method-2(USING DIVIDE AND CONQURE  CONCEPT)

when we divide an array into left half and right half and merge them
so total number of inversions equal to the =number of inversion in left part
+number of inversion in right part + number of inversion in merging part

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

#include <bits/stdc++.h> using namespace std; #define LL long long int LL merge_array(LL a[],LL temp[],LL low,LL mid,LL high) { LL i,j,k,count=0,p=mid-1; for(i=low;i<=high;i++) temp[i]=a[i]; i=low; j=mid; k=low; while(i<=p && j<=high) { if(temp[i]<=temp[j]) a[k++]=temp[i++]; else { a[k++]=temp[j++]; count+=(mid-i); } } while(i<=p) a[k++]=temp[i++]; while(j<=high) a[k++]=temp[j++]; return count; } LL merge_sort(LL a[],LL temp[],LL l,LL r) { LL mid,count=0; if(l<r) { mid=(l+r)>>1; count=merge_sort(a,temp,l,mid); count+=merge_sort(a,temp,mid+1,r); count+=merge_array(a,temp,l,mid+1,r); } return count; } LL _merge_sort(LL a[],LL n) { LL *temp=(LL *)malloc(sizeof(LL)*n); return merge_sort(a,temp,0,n-1); } int main() { LL t,n,i; scanf("%lld",&t); while(t--) { scanf("%lld",&n); LL a[n]; for(i=0;i<n;i++) scanf("%lld",&a[i]); printf("%lld\n",_merge_sort(a,n)); } return 0; }