<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 Node {
public:
    long val;
    size_t count, lCount = 0, rCount = 0;
    Node* left = nullptr, *right = nullptr;
    Node* parent;
    Node(long val, int count, Node* parent) : val(val), count(count), parent(parent) {}
    void printNode() {
        cout << "(" << val << ", " << count << ", " << lCount << ", " << rCount << ") ";
    }
    void print() {
        cout << "{";
        printNode();
        if (this->left == nullptr)
            cout << "{} ";
        else
            this->left->print();
        if (this->right == nullptr)
            cout << "{} ";
        else
            this->right->print();
        cout << "} ";
    }
};

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        map<long, int> numCounts;
        for (const auto& num: nums) numCounts[num]++;
        vector<pair<long, int>> numCountsVec(numCounts.begin(), numCounts.end());
        Node* head = buildBST(numCountsVec, 0, numCounts.size()-1, nullptr);
        int total = 0;
        for (int i = 0; i < nums.size(); i++) {
            long num = nums[i];
            decrementCount(findLowerBound(head, num));
            long target = (num > 0) ? ((num - 1) / 2) : ((num - 2) / 2);
            int targetCount = countLessThanEqualTo(head, target);
            total += targetCount;
        }
        return total;
    }

    void decrementCount(Node* node, Node* child = nullptr) {
        if (node == nullptr) return;
        if (child == nullptr) node->count--;
        else if (child == node->left) node->lCount--;
        else if (child == node->right) node->rCount--;
        decrementCount(node->parent, node);
    }

    int countLessThanEqualTo(Node* head, long val) {
        if (head == nullptr) return 0;
        if (head->val > val) return countLessThanEqualTo(head->left, val);  
        return head->count + head->lCount + (head->val == val ? 0 : countLessThanEqualTo(head->right, val));
    }

    Node* findLowerBound(Node* head, long val) {
        if (head == nullptr) return nullptr;
        if (head->val < val) return findLowerBound(head->right, val);
        if (head->val == val) return head;

        Node* lbLeft = findLowerBound(head->left, val);
        if (lbLeft == nullptr) return head;
        if (lbLeft->val < head->val) return lbLeft;
        return head;
    }

    Node* buildBST(vector<pair<long, int>>& numCountsVec, int start, int end, Node* parent) {
        if (start > end) return nullptr;
        int m = (start + end) / 2;
        Node* head = new Node(numCountsVec[m].first, numCountsVec[m].second, parent);
        head->left = buildBST(numCountsVec, start, m-1, head);
        head->right = buildBST(numCountsVec, m+1, end, head);
        if (head->left != nullptr)
            head->lCount = head->left->count + head->left->lCount + head->left->rCount;
        if (head->right != nullptr)
            head->rCount = head->right->count + head->right->lCount + head->right->rCount;
        return head;
    }
};
92963