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

离散化+线段树+python

MOD = 1000000007

class SegmentTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (4 * size)
    
    def update(self, index, delta, node=1, left=1, right=None):
        if right is None:
            right = self.n
        
        # 找到叶子节点
        if left == right:
            self.tree[node] = (self.tree[node] + delta) % MOD
            return
        
        # 递归更新
        mid = (left + right) // 2
        if index <= mid:
            self.update(index, delta, 2 * node, left, mid)
        else:
            self.update(index, delta, 2 * node + 1, mid + 1, right)
        
        # 更新父节点
        self.tree[node] = (self.tree[2 * node] + self.tree[2 * node + 1]) % MOD
    
    def query(self, l, r, node=1, left=1, right=None):
        if right is None:
            right = self.n
        
        # 查询区间完全在节点区间外
        if r < left or l > right:
            return 0
        
        # 查询区间完全包含节点区间
        if l <= left and right <= r:
            return self.tree[node]
        
        # 递归查询左右子树
        mid = (left + right) // 2
        left_sum = self.query(l, r, 2 * node, left, mid)
        right_sum = self.query(l, r, 2 * node + 1, mid + 1, right)
        
        return (left_sum + right_sum) % MOD

class Solution:
    def InversePairs(self, data):
        if not data:
            return 0
        
        # 离散化处理
        sorted_data = sorted(data)
        mapping = {val: idx + 1 for idx, val in enumerate(sorted_data)}
        
        # 初始化线段树
        n = len(data)
        seg_tree = SegmentTree(n)
        
        # 逆序遍历数组
        count = 0
        for i in range(len(data) - 1, -1, -1):
            num = data[i]
            pos = mapping[num]
            
            # 查询比当前数小的元素个数（已经处理过的）
            if pos > 1:
                count = (count + seg_tree.query(1, pos - 1)) % MOD
            
            # 更新线段树
            seg_tree.update(pos, 1)
        
        return count % MOD