### Inversion count

Question-
https://www.spoj.com/problems/INVCNT/

Method I used-
Counting no of inversions using merge sort

Problem-
I can't figure out why my answer comes wrong.
I am adding m-i to inv in line 25

 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374`` `````` #include 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=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>arr[i]; int inv=mergesort(arr,0,n-1); cout<
Last edited on
`inv+=n1-i;`

keep in mind what your variables represent and what values may it hold
you work on the array on the portion [l, m], you copy that range to another array so you transform [l, m] to [0, n1)
so, `i' traverses the range [0, n1) and you want to know how many elements are to the right of `i'
that's `n1-i'