Reverse Pairs

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.

Solution:

class Solution {
    static class BIT {
        int[] arr;
        
        public BIT(int n) {
            arr = new int[n + 1];
        }
        
        public void update(int idx, int val) {
            idx += 1;
            // update tree that includes indx in left subtree
            while (idx < arr.length) {
                arr[idx] += val;
                idx += (idx & -idx);
            }
        }
        
        public int query(int idx) {
            int res = 0;
            idx += 1;
            while (idx > 0) {
                res += arr[idx];
                idx -= (idx & -idx);
            }
            return res;
        }
    }
    
    public int reversePairs(int[] nums) {
        TreeSet<Long> set = new TreeSet();
        for (int i = 0; i < 2 * nums.length; i ++) {
            if (i < nums.length) set.add((long) nums[i]);
            else set.add(2 * (long) nums[i - nums.length]);
        }
        long[] sorted = new long[set.size()];
        for (int i = 0; i < sorted.length; i ++) {
            sorted[i] = set.pollFirst();
        }
        BIT bit = new BIT(sorted.length);
        int res = 0;
        for (int i = nums.length - 1; i >= 0; i --) {
            long num = (long) nums[i];
            int rank = Arrays.binarySearch(sorted, num) + 1;
            int dRank = Arrays.binarySearch(sorted, 2 * num) + 1;
            // count number of 2 * prevNum smaller than rank
            res += bit.query(rank - 1);
            bit.update(dRank, 1);
        }
        return res;
    }
}