// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem315.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=315 lang=cpp
 *
 * [315] 计算右侧小于当前元素的个数
 */

// @lc code=start
class Solution {
public:
    vector<int> res;
    vector<pair<int, int>> sort_nums;

    void sort(vector<pair<int, int>>& temp, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(temp, lo, mid);
        sort(temp, mid + 1, hi);
        merge(temp, lo, mid, hi);
    }

    void merge(vector<pair<int, int>>& temp, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        int k = lo;

        while (i <= mid && j <= hi) {
            if (temp[i].first <= temp[j].first) {
                res[temp[i].second] += j - mid - 1;
                sort_nums[k++] = temp[i++];
            } else {
                sort_nums[k++] = temp[j++];
            }
        }
        while (j <= hi) {
            sort_nums[k++] = temp[j++];
        }
        while (i <= mid) {
            res[temp[i].second] += j - mid - 1;
            sort_nums[k++] = temp[i++];
        }
        for (i = lo; i <= hi; i++) {
            temp[i] = sort_nums[i];
        }
    }

    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<pair<int, int>> temp;
        for (int i = 0; i < n; i++) {
            temp.emplace_back(pair<int, int>(nums[i], i));
        }
        res = vector<int>(n, 0);
        sort_nums = vector<pair<int, int>>(n);
        sort(temp, 0, n - 1);
        return res;
    }
};
// @lc code=end