Reverse Pairs -- LeetCode 493

[Question]

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2

Example2:

Input: [2,4,3,5,1]
Output: 3

Note:

1. The length of the given array will not exceed 50,000.
2. All the numbers in the input array are in the range of 32-bit integer.

[Analysis]
This is a typical problem for Binary Index Tree (BIT). Another solution is to use a BST with a smaller counter in each node -- but this solution will make time complexity O(N*N) for sorted input array. BIT is still a better solution.

[Solution]
class BIT {
    vector<int> nodes;
    int lowbit(int x) { return -x & x; }
public:
    BIT(int n) : nodes(n+1,0) {};
 
    void add(int pos, int val) {
        while (pos<nodes.size()) {
            nodes[pos]+=val;
            pos += lowbit( pos );
        }
    }
 
    int count(int pos) {
        int res =0;
        while (pos>0) {
            res += nodes[pos];
            pos -= lowbit( pos );
        }
        return res;
    }
};

typedef long long LL;

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        vector<pair<LL,int> > sorted;
        for (int i=0; i<nums.size(); i++) {
            sorted.push_back({(LL)nums[i],i+1});
            sorted.push_back({(LL)nums[i]<<1, -i-1});
        }
        sort(sorted.begin(), sorted.end(), [](pair<LL,int>& a, pair<LL,int>& b) {
            return a.first< b.first || a.first==b.first && a.second>b.second;
        });
     
        unordered_map<LL,int> map;
        for (int i=0; i<sorted.size(); i++)
            map[sorted[i].second] = i;
     
     
        BIT tree(sorted.size());
        int res=0;
        for (int i=nums.size()-1; i>=0; i--) {
            res += tree.count(map[i+1]);
            tree.add(map[-i-1]+1,1);
        }
        return res;
    }
};