Count inversion pair in array range 1 to n
Problems:
Give an array[1..n], a pair call inversion if with i, j (1 <= i <j <= n) and (array[i] > array[j]) counting how many inversions pair?
Solution:Use divide and conquer (Hint: same with merge sort)
C++ source code:
/** * Brute Force * Complexity O(n^2) * **//** * * Count Inversion by Merger Algorithms * Complexity O(nlog(n)) * **/#include<iostream>#include<cstdio>#include<cassert>usingnamespacestd;constint__OO__=1e9+7;constintSIZE=1e6+5;intn,a[SIZE];intbrute_force(intA[],intLen){intinv=0;for(inti=1;i<Len;i++)for(intj=i+1;j<=Len;j++)if(A[i]>A[j])++inv;returninv;}intMERGE_INVERSIONS(intA[],intp,intq,intr){intn1=q-p+1,n2=r-q;intL[n1+1],R[n2+1];for(inti=1;i<=n1;i++)L[i]=A[p+i-1];for(intj=1;j<=n2;j++)R[j]=A[q+j];L[n1+1]=__OO__,R[n2+1]=__OO__;inti=1,j=1;intmInv=0;boolcounted=false;for(intk=p;k<=r;k++){if(!counted&&R[j]<L[i]){mInv+=n1-i+1;counted=true;}if(L[i]<=R[j]){A[k]=L[i];i++;}else{A[k]=R[j];j++;counted=false;}}returnmInv;}intCOUNT_INVERSIONS(intA[],intp,intr){intinv=0;if(p<r){intq=p+(r-p)/2;inv+=COUNT_INVERSIONS(A,p,q);inv+=COUNT_INVERSIONS(A,q+1,r);inv+=MERGE_INVERSIONS(A,p,q,r);}returninv;}intmain(){assert(freopen("INVERSIONS.INP","r",stdin));cin>>n;for(inti=1;i<=n;i++)cin>>a[i];//cout << brute_force(a, n) << endl;cout<<COUNT_INVERSIONS(a,1,n)<<endl;return0;}