题解 | #右侧更小数#

{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
  public:
    vector<int> index;
    vector<int> temp;
    vector<int> tempIndex;
    vector<int> ans;

    void Merge(vector<int>& a, int l, int mid, int r) {
        int i = l, j = mid + 1, p = l;
        while (i <= mid && j <= r) {
            if (a[i] <= a[j]) {
                temp[p] = a[i];
                tempIndex[p] = index[i];
                ans[index[i]] += (j - mid - 1);
                ++i;
                ++p;
            } else {
                temp[p] = a[j];
                tempIndex[p] = index[j];
                ++j;
                ++p;
            }
        }
        while (i <= mid) {
            temp[p] = a[i];
            tempIndex[p] = index[i];
            ans[index[i]] += (j - mid - 1);
            ++i;
            ++p;
        }

        while (j <= r) {
            temp[p] = a[j];
            tempIndex[p] = index[j];
            ++j;
            ++p;
        }

        for (int k = l; k <= r; ++k) {
            index[k] = tempIndex[k];
            a[k] = temp[k];
        }
    }

    void MergeSort(vector<int>& a, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) >> 1;
        MergeSort(a, l, mid);
        MergeSort(a, mid + 1, r);
        Merge(a, l, mid, r);
    }

    vector<int> smallerCount(vector<int>& nums) {
        index.resize(nums.size()); //存放原数组各元素对应的下标
        temp.resize(nums.size()); //原数组的副本
        tempIndex.resize(nums.size()); //存放副本数组各元素对应的下标
        ans.resize(nums.size()); //存放最终结果

        for (int i = 0; i < nums.size(); ++i) {
            index[i] = i;
        }

        int l = 0, r = nums.size() - 1;
        MergeSort(nums, l, r); //归并排序
        return ans;
    }
};