题解 | #数组中的逆序对#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int InversePairs(vector<int>& nums) {
    const int threshold = 1000000007;
    int n = nums.size();
    int ret = 0;
    //非递归形势将左右下标入栈，时间空间logn
    stack<pair<int, int>> st;
    stack<pair<int, int>> tempStack;
    tempStack.emplace(0,n-1);

    while (!tempStack.empty()) {
        auto [l, r] = tempStack.top();
        tempStack.pop();
        st.emplace(l, r);

        if (l + 1 < r) {
            int mid = (l + r) >> 1;
            tempStack.emplace(mid + 1, r);
            tempStack.emplace(l, mid);
        }
    }

    while (!st.empty()) {
        auto [left, right] = st.top();
        st.pop();
        if (left == right) continue;
        else if (left + 1 == right) {
            if (nums[left] > nums[right]) {
                ret++;
                swap(nums[left], nums[right]);
                continue;
            }
            continue;
        } else {
            int mid = (left + right) >> 1;
            int i = mid, j = right;
            int tmp = 0;
            while (j > mid) {//
                while (i >= left && nums[i] > nums[j]) {
                    tmp++;
                    i--;
                }
                ret += tmp;
                j--;
            }
            sort(nums.begin() + left, nums.begin() + right + 1);
        }
        ret%=threshold;
    }
    return ret;
}
};