0493. Reverse Pairs.md

493. Reverse Pairs, hard

tags: BIT, Binary Indexed Tree, Fenwick Tree

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: The length of the given array will not exceed 50,000. All the numbers in the input array are in the range of 32-bit integer.

// 264ms, 65%, slow & easy version
class Solution {
private:
    void update(vector<int>& ar, int i, int delta) {
        for(; i < ar.size(); i += i & -i) {
            ar[i] += delta;
        }
    }
    int query(vector<int>& ar, int i) {
        int sum = 0;
        for(; i > 0; i -= i & -i) {
            sum += ar[i];
        }
        return sum;
    }
public:
    int reversePairs(vector<int>& nums) {
        // pair: <orig_value, orig_pos>
        vector<int> nums_sort(nums);
        sort(nums_sort.begin(), nums_sort.end());

        vector<int> c_nums(nums.size()+1, 0);
        int res = 0;
        for (int i = nums.size()-1; i >= 0; i--) {
            const auto val = nums[i];
            int smallV = val %2 == 0? val/2 - 1 : (val > 0? val/2: (val-1)/2);
            auto it = lower_bound(nums_sort.begin(), nums_sort.end(), smallV);
            if (it == nums_sort.end() || *it > smallV)
                --it;
            if (it >= nums_sort.begin()) {
                int rank = it - nums_sort.begin() + 1;
                res += query(c_nums, rank);
            }
            
            update(c_nums, lower_bound(nums_sort.begin(), nums_sort.end(), nums[i]) - nums_sort.begin() + 1, 1);
        }
        return res;
    }
};

// 240ms, 75%
class Solution {
private:
    void update(vector<int>& ar, int i, int delta) {
        for(; i < ar.size(); i += i & -i) {
            ar[i] += delta;
        }
    }
    int query(vector<int>& ar, int i) {
        int sum = 0;
        for(; i > 0; i -= i & -i) {
            sum += ar[i];
        }
        return sum;
    }
public:
    int reversePairs(vector<int>& nums) {
        // pair: <orig_value, orig_pos>
        vector<pair<int,int>> nums_sort(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            nums_sort[i] = {nums[i], i};
        }
        sort(nums_sort.begin(), nums_sort.end());

        // pair: <value, rank>, same value use the same rank
        int starti = 0;
        vector<pair<int,int>> nums_copy(nums.size());
        for (int i = 0; i < nums_sort.size(); i++) {
            auto& pp = nums_sort[i];
            int rank;
            if (i > 0 && pp.first == nums_sort[i-1].first) {
                rank = starti + 1;
            } else {
                starti = i;
                rank = i + 1;
            }
            nums_copy[pp.second] = {nums[pp.second], rank};
        }
        
        vector<int> c_nums(nums.size()+1, 0);
        int res = 0;
        for (int i = nums_copy.size()-1; i >= 0; i--) {
            const auto val = nums_copy[i].first;
            int smallV = val %2 == 0? val/2 - 1 : (val > 0? val/2: (val-1)/2);
            auto it = lower_bound(nums_sort.begin(), nums_sort.end(), smallV, [&i](auto& a, auto& b) {
                return a.first < b; });
            if (it == nums_sort.end() || it->first > smallV)
                --it;
            if (it >= nums_sort.begin()) {
                int rank = it - nums_sort.begin() + 1;
                res += query(c_nums, rank);
            }
            
            update(c_nums, nums_copy[i].second, 1);
        }
        return res;
    }
};