<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:
    int reversePairs(vector<int>& nums) {
        return count(nums, 0, nums.size()-1);
    }

    int count(vector<int>& nums, int start, int end) {
        if (start == end) return 0;
        if (start == end-1) {
            int result = (nums[start]/2.0 > nums[end]);
            if (nums[start] > nums[end]) swap(nums[start], nums[end]);
            return result;
        }

        int mid = start + (end-start)/2;
        int left_count = count(nums, start, mid);
        int right_count = count(nums, mid+1, end);
        int left_ind = start, right_ind = mid+1;
        int result = left_count + right_count;
        while (left_ind <= mid) {
            while (right_ind <= end && nums[left_ind]/2.0 > nums[right_ind]) {
                right_ind++;
            }
            result += right_ind - mid - 1;
            left_ind++;
        }

        // merge 2 part
        left_ind = start; right_ind = mid+1;
        vector<int> merged;
        while (left_ind <= mid && right_ind <= end) {
            if (nums[left_ind] <= nums[right_ind]) {
                merged.push_back(nums[left_ind++]);
            } else {
                merged.push_back(nums[right_ind++]);
            }
        }
        while (left_ind <= mid)
            merged.push_back(nums[left_ind++]);
        while (right_ind <= end)
            merged.push_back(nums[right_ind++]);

        int final_ind = start;
        for (int i = 0; i < merged.size(); ++i, ++final_ind)
            nums[final_ind] = merged[i];

        return result;
    }
};
195495