Description

Submission

class Solution {
    vector<int> counts;
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        counts.resize(n, 0);
        auto sorted = nums;
        divideConquer(sorted, nums, 0, n-1);
        return counts;
    }

    void divideConquer(vector<int>& sorted, vector<int>& nums, int start, int end)
    {
        if(start >= end) return;

        int mid = (start + end) / 2;
        divideConquer(sorted, nums, start, mid);
        divideConquer(sorted, nums, mid+1, end);

        for(int i = start; i <= mid; ++i) {
            auto iter = lower_bound(sorted.begin()+mid+1, sorted.begin()+end+1, nums[i]);
            counts[i] += iter - (sorted.begin() + mid + 1);
        }

        sort(sorted.begin() + start, sorted.begin() + end + 1);
    }
};