题目描述
blablabla
样例
class Solution(object):
# 以下是树状数组基本结构
def lowbit(self, x):
return x & (-x)
def add(self, x, v):
i = x
while i <= self.n:
self.C[i] += v
i += self.lowbit(i)
def sum(self, x):
res = 0
i = x
while i > 0:
res += self.C[i]
i -= self.lowbit(i)
return res
# 主程序
def inversePairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
sub_nums = sorted(nums)
self.n = len(set(sub_nums))
ans = 0
self.C = [0 for _ in range(self.n + 1)]
for i in range(len(nums)):
nums[i] = sub_nums.index(nums[i]) + 1 # 离散化 找到未排序的数组中的数在排序后的数组中的编号 即可实现离散化
ans += self.sum(self.n) - self.sum(nums[i])
self.add(nums[i], 1)
return ans