490. Reverse Pair

Problem Link

Tutorial

First, do the discretization. The discretization array should taken into account both nums[i] and nums[i] * 2.

Then, insert the elements into binary indexed tree from left. Before inserting nums[i], we should check how many elements in the binary indexed tree is greater than nums[i] * 2, and add it to the final answer.

From this problem, we can generalize the discretization method. It can discretize not only the elements of an array, but also some other elements together and keep their relations (greater, less). Note: Multiset will cause TLE since std::distance would take linear time to the size of the multiset.

Solution

class Discrete:

    def __init__(self, f):
        self.f = list(set(f))
        self.f.sort()

    def index(self, a):
        import bisect
        return bisect.bisect_left(self.f, a)

class BITree:

    def __init__(self, n):
        self.f = [0]*(n+3)
        self.n = n + 2

    def sum(self, pos=None):
        if not pos:
            i = self.n
        else:
            i = pos
        s = 0  #initialize result
        while i > 0:
            s += self.f[i]
            i -= i & (-i)
        return s

    def update(self, pos ,value):
        i = pos
        while i <= self.n:
            self.f[i] += value
            i += i & (-i)

class Solution(object):
    def reversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums2 = nums + list(map(lambda x: x * 2, nums))
        d = Discrete(nums2)
        bit = BITree(len(d.f))
        ret = 0
        for x in nums:
            index = d.index(x) + 1
            ret += bit.sum() - bit.sum(d.index(x * 2) + 1)
            bit.update(index, 1)
        return ret

#print(Solution().reversePairs([-5,-5]))
#print(Solution().reversePairs([1,3,2,3,1]))
#print(Solution().reversePairs([]))
#print(Solution().reversePairs([2,4,3,5,1]))

#define d(x) 
#define LL long long
#define MAX_N (int(5e4 + 10) * 2)
struct BIT
{
    LL binary_indexed_tree[MAX_N];

    void init()
    {
        memset(binary_indexed_tree, 0, sizeof(binary_indexed_tree));
    }

    int low_bit(int x)
    {
        return x & (-x);
    }

    void add(int pos, LL val)
    {
        for (int i = pos; i < MAX_N; i += low_bit(i))
        {
            binary_indexed_tree[i] += val;
        }
    }

    LL sum(int pos)
    {
        LL ret = 0;
        for (int i = pos; i > 0; i -= low_bit(i))
        {
            ret += binary_indexed_tree[i];
        }
        return ret;
    }
};


class Solution {
public:
    int reversePairs(vector<int>& nums) {
        vector<long long> discrete = vector<long long> ();
        for (int i = 0; i < (int)nums.size(); i++) {
            discrete.push_back(nums[i]);
            discrete.push_back(nums[i] * 2LL);
        }
        sort(discrete.begin(), discrete.end());
        discrete.resize(std::distance(discrete.begin(), unique(discrete.begin(), discrete.end())));

        BIT bit = BIT();
        bit.init();
        int ret = 0;
        for (int i = 0; i < (int)nums.size(); i++) {
            long long a = lower_bound(discrete.begin(), discrete.end(), nums[i]) - discrete.begin() + 1;
            long long a2 = lower_bound(discrete.begin(), discrete.end(), nums[i] * 2LL) - discrete.begin() + 1;
            ret += bit.sum(MAX_N - 1) - bit.sum(a2);
            bit.add(a, 1);
            d(cout << a2 << endl);
        }
        return ret;
    }
};