<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 SegmentTree:
    def __init__(self, n: int) -> None:
        self.tree = [0]*(4*n)
        self.tags = [0]*(4*n)
        self.n = n
        
    def _pushdown(self, s: int, mid: int, e: int, idx: int) -> None:
        if self.tags[idx] != 0:
            self.tags[2*idx] += self.tags[idx]
            self.tags[2*idx+1] += self.tags[idx]
            self.tree[2*idx] += self.tags[idx] * (mid-s+1)
            self.tree[2*idx+1] += self.tags[idx] * (e-mid)
            self.tags[idx] = 0
        
    def _query(self, t_s: int, t_e: int, s: int, e: int, idx: int) -> int:
        if t_s <= s and t_e >= e:
            return self.tree[idx]
        elif t_s > e or t_e < s:
            return 0
        else:
            mid = (s+e)//2
            self._pushdown(s, mid, e, idx)
            left = self._query(t_s, t_e, s, mid, 2*idx)
            right = self._query(t_s, t_e, mid+1, e, 2*idx+1)
            return left+right
    
    def query(self, start: int, end: int) -> int:
        return self._query(start, end, 0, self.n-1, 1)
    
    def _update(self, t_s: int, t_e: int, s: int, e: int, idx: int, val: int) -> None:
        if t_s <= s and t_e >= e:
            self.tree[idx] += (e-s+1)*val
            self.tags[idx] += val
        elif t_s > e or t_e < s:
            return
        else:
            mid = (s+e)//2
            self._pushdown(s, mid, e, idx)
            self._update(t_s, t_e, s, mid, 2*idx, val)
            self._update(t_s, t_e, mid+1, e, 2*idx+1, val)
            self.tree[idx] = self.tree[2*idx] + self.tree[2*idx+1]
    
    def update(self, start: int, end: int, val: int) -> None:
        self._update(start, end, 0, self.n-1, 1, val)
        
class Solution:
    def proprocess(self, nums: List[int]) -> Tuple[List[int], Dict[int, int]]:
        nums_copy = list(set(nums))
        nums_copy.sort()
        mapping = {}
        for i, num in enumerate(nums_copy):
            mapping[num] = i
        distincts = nums_copy
        return distincts, mapping
    
    def search(self, num: int) -> int:
        if 2*self.distincts[0] >= num:
            return -1
        lo, hi = 0, len(self.distincts)-1
        while lo < hi:
            mid = (lo+hi)//2
            if 2 * self.distincts[mid] < num:
                lo = mid+1
            else:
                hi = mid
        if lo >= len(self.distincts) or 2*self.distincts[lo] >= num:
            return lo-1
        else:
            return lo
    
    def reversePairs(self, nums: List[int]) -> int:
        self.distincts, self.mapping = self.proprocess(nums)
        self.n = len(self.mapping)
        sg_tree = SegmentTree(self.n)
        total = 0
        for i in range(len(nums)-1, -1, -1):
            q_idx = self.search(nums[i])
            if q_idx != -1:
                res = sg_tree.query(0, q_idx)
                total += res
            c_idx = self.mapping[nums[i]]
            sg_tree.update(c_idx, c_idx, 1)
        return total
30400