题解 | 数组中的逆序对

from re import I
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def InversePairs(self , nums: List[int]) -> int:
        MOD = 1000000007
        right_sorted = []
        count = 0
        
        for x in reversed(nums):
            # 手动二分查找插入位置
            lo, hi = 0, len(right_sorted)
            while lo < hi:
                mid = (lo + hi) // 2
                if right_sorted[mid] < x:
                    lo = mid + 1
                else:
                    hi = mid
            pos = lo  # 第一个 >= x 的位置
            count = (count + pos) % MOD
            right_sorted.insert(pos, x)
        
        return count % MOD