493

class Solution {
private:
    int getSum(int *bit, int idx){
        int sum = 0;
        while(idx > 0){
            sum += bit[idx];
            idx -= (idx&-idx);
        }
        return sum;
    }

    void update(int *bit, int n, int idx, int val){
        while(idx <= n){
            bit[idx] += val;
            idx += (idx & -idx);
        }
    }

public:
    int reversePairs(vector<int>& nums) {
        if (!nums.size()) return 0;
        int n = nums.size(), inversions = 0;
        int temp[n];
        for(int i=0; i<n; i++)
            temp[i] = nums[i];

        sort(temp, temp+n);
        int bit[50004] = {0};

        for(int i=0; i<n; i++){
            int index = upper_bound(temp, temp+n, 2L * nums[i]) - temp;
            inversions += i - getSum(bit, index);
            index = upper_bound(temp, temp+n, nums[i]) - temp;
            update(bit, n, index, 1);
        }
        return inversions;
    }
};