<p>Given an integer array <code>nums</code>, return <em>the number of <strong>reverse pairs</strong> in the array</em>.</p>

<p>A <strong>reverse pair</strong> is a pair <code>(i, j)</code> where:</p>

<ul>
	<li><code>0 &lt;= i &lt; j &lt; nums.length</code> and</li>
	<li><code>nums[i] &gt; 2 * nums[j]</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,2,3,1]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The reverse pairs are:
(1, 4) --&gt; nums[1] = 3, nums[4] = 1, 3 &gt; 2 * 1
(3, 4) --&gt; nums[3] = 3, nums[4] = 1, 3 &gt; 2 * 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,4,3,5,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The reverse pairs are:
(1, 4) --&gt; nums[1] = 4, nums[4] = 1, 4 &gt; 2 * 1
(2, 4) --&gt; nums[2] = 3, nums[4] = 1, 3 &gt; 2 * 1
(3, 4) --&gt; nums[3] = 5, nums[4] = 1, 5 &gt; 2 * 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution {
public:
#define ll long long int
ll merge(vector<ll>&a, vector<ll>&b, vector<ll>&v){
    ll c=0;
    ll i=0, j=0, k=0, l=-1;
    while(i<a.size()&&j<b.size())
    {
        
      
        if(a[i]<b[j]){
            v[k]=a[i];
            i++;k++;
        }
        else{
            v[k]=b[j];
            k++;
            j++;
        }        
    }
    if(i==a.size())
    {
        while(j<b.size()){
            v[k]=b[j];
            k++;
            j++;
        }
    }
    if(j==b.size())
    {
        while(i<a.size())
        {
           v[k]=a[i];
            i++;k++; 
        }
    }
    for(ll e=0; e<b.size(); e++)    
    {
          ll f=-1;
          ll hi=a.size()-1;
          ll lo=0;
          while(lo<=hi)
          {
            ll mid=lo+(hi-lo)/2;
            if(a[mid]>2*b[e]){
                f=a.size()-mid;
                hi=mid-1;

            }
            else lo=mid+1;
          }
          if(f!=-1)c+=f;
    }
    return c;
}
ll mergesort(vector<ll> &nums)
{
    if(nums.size()>1)
    {
        ll n=nums.size();
        ll n1=n/2;
        ll n2=n-n1;
        // cout<<n1<<" "<<n2<<endl;
       vector<ll>a(n1),b(n2);
       for(ll i=0; i<n1; i++){a[i]=nums[i];}
       
       for(ll i=0; i<n2; i++){b[i]=nums[n1+i];}
       ll count =0;
       count+=mergesort(a);
       count+=mergesort(b);
       count+=merge(a,b,nums);
       a.clear();
       b.clear();
       return count;
      
    }
    return 0;
}
    int reversePairs(vector<int>& nums) {
        vector<ll> nu;
        for(ll ele:nums)nu.push_back((ll)ele);
         return mergesort(nu);
    }
};
175965