**Inversions Revisited

Inversions Revisited

---

 

• Algorithms
• BIT
• Hard

Most of us know how to count the number of inversions in an array. An inversion in an array is a pair of indices(i,j) such that a[i]>a[j] and i < j.

In this problem you are given 2 arrays A and B and you have to return number of such pairs such that a[i]>b[j] and i < j.

Input Format:

First line contains n denoting the total number of elements.The next line contains n space separated integers of array A.This line is again followed by n space separated integers of array B.

Output Format:

Print the total number of pairs satisfying the above condition.

Constraints:

1<=n<=200000

1<=A[i]<=10^6

1<=B[i]<=10^6

---

Sample Input

(Plaintext Link)

3
5 6 7
1 2 3

Sample Output

(Plaintext Link)

3

Explanation

3 pairs are (5,2) , (5,3) and (6,3).

***************************EDITORIAL***********************************************************

IN THIS PROBLEM WE NEED TO DO  INVERSION COUNT IN A BIT  CHANGED WAY

SINCE A[I] CAN FORM INVERSION WITH B[J] WHERE J>I ANS A[I]>B[J] .. SOO PART IN WHICH WE DO CALCULATION OF INVERSION COUNT ,  LEFT PART WE USE A[] AND FOR RIGHT PART WE USE B[] . 

AFTER IC CALCULATION INDIVIDUALLY COMPARE AND SORT BOTH ARRAY ..

*****************************************************************************************************

#include<iostream>
using namespace std;
 typedef long long int lli;
 #include<bits/stdc++.h>
 lli ic=0;
    lli temp[1000000];
    lli arr[1000000+10];
      lli brr[1000000+10];
lli merge (lli arr[],lli brr[],lli start,lli mid,lli end)
   {
   
     lli i=start, 
j=mid+1;
     lli p=start;
   
      lli lc=0;
       while(i<=mid && j<=end)
        {
       
        if(arr[i]>brr[j])// calculation inversion in arr[] and brr[]
        {
        lc+=mid-i+1;
       
        j++;
}
else
{

i++;
}
       
}


//sorting arr
i=start, 
j=mid+1;
         p=start;

while(i<=mid && j<=end)
        {
       
        if(arr[i]>arr[j])
        {
       
        temp[p++]=arr[j];
        j++;
}
else
{
temp[p++]=arr[i++];
 
}
       
}

while(i<=mid) temp[p++]=arr[i++];
while(j<=end) temp[p++]=arr[j++];
for(int i=start;i<p;i++) arr[i]=temp[i];


//sorting brr
i=start, 
j=mid+1;
         p=start;

while(i<=mid && j<=end)
        {
       
        if(brr[i]>brr[j])
        {
       
        temp[p++]=brr[j];
        j++;
}
else
{
temp[p++]=brr[i++];
 
}
       
}

while(i<=mid) temp[p++]=brr[i++];
while(j<=end) temp[p++]=brr[j++];
for(int i=start;i<p;i++) brr[i]=temp[i];
return lc;
   }
  
 void  divide(lli arr[],lli brr[],lli start,lli end)
  {
   
  if(start<end)
  {
   
  lli mid=(start+end)/2;
   
  divide(arr,brr,start,mid);
  divide(arr,brr,mid+1,end);
  ic+=merge(arr,brr,start,mid,end);
  }
   

  }
  
 int  main()
  {
  
    ic=0;
    lli n;
    cin>>n;
      
    for(int i=0;i<n;i++)
     {
       cin>>arr[i];
        
 }
  for(int i=0;i<n;i++)
           {
           cin>>brr[i];
        
     }
 divide(arr,brr,0,n-1);
  cout<<ic<<endl;

return 0;
  }