计算逆序数有两种思路，一种是统计归并排序过程中交换的次数，另一种是根据rank逐个修改位置计数，当前rank的逆序数等于[rank + 1, n]的区间和
leetcode有一个弱模板题
class Solution:
def reversePairs(self, record: List[int]) -> int:
a = record
if a == []:
return 0
global ans
ans = 0
def change(nums1, nums2):
global ans
p1 = 0
p2 = 0
n = len(nums1)
m = len(nums2)
res = []
while p1 < n and p2 < m:
if nums1[p1] > nums2[p2]:
res.append(nums2[p2])
p2 += 1
ans += (n - p1)
else:
res.append(nums1[p1])
p1 += 1
res.extend(nums1[p1: ])
res.extend(nums2[p2: ])
return res
def merge(nums):
n = len(nums)
if n == 1:
return nums
left = 0
right = n - 1
mid = (left + right) // 2
l = merge(nums[: mid + 1])
r = merge(nums[mid + 1: ])
return change(l, r)
merge(a)
return ans
一般来说面试像上面那么写就行了，但是这种归并写法会不断复制列表导致开销是很大，如果是竞赛题这么写就不行，需要用索引归并，最后复制一次
这种做法也是我试过python唯一能过洛谷模板题的写法，洛谷很多题给的时间都把python卡掉了，这种专注竞赛的平台几乎都是c++专场
class Solution:
def reversePairs(self, record: List[int]) -> int:
a = record
if a == []:
return 0
global ans
ans = 0
res = [0] * len(a)
def change(l, mid, r):
global ans
p1 = l
p2 = mid + 1
n = mid - l + 1
k = l
while p1 <= mid and p2 <= r:
if a[p1] > a[p2]:
res[k] = a[p2]
p2 += 1
ans += (n - p1 + l)
else:
res[k] = a[p1]
p1 += 1
k += 1
while p1 != mid + 1:
res[k] = a[p1]
k += 1
p1 += 1
while p2 != r + 1:
res[k] = a[p2]
k += 1
p2 += 1
for i in range(l, r + 1):
a[i] = res[i]
def merge(left, right):
if left >= right:
return
mid = (left + right) // 2
merge(left, mid)
merge(mid + 1, right)
change(left, mid, right)
merge(0, len(a) - 1)
return ans
第二种做法需要单点修改和区间求和，写了线段树和树状数组两种写法
线段树：
class Solution:
def reversePairs(self, record: List[int]) -> int:
a = record
class segment_tree:
def __init__(self, nums):
n = len(nums)
self.nums = nums
self.tree = [0] * 4 * n
def update(self, root):
self.tree[root] = self.tree[root * 2] + self.tree[root * 2 + 1]
def build(self, left, right, root):
if left > right:
return
if left == right:
self.tree[root] = self.nums[left - 1]
return
mid = (left + right) // 2
self.build(left, mid, root * 2)
self.build(mid + 1, right, root * 2 + 1)
self.update(root)
def change(self, A, v, left, right, root):
if left > right:
return
if left == right:
self.tree[root] = v
return
mid = (left + right) // 2
if left <= A <= mid:
self.change(A, v, left, mid, root * 2)
if mid + 1 <= A <= right:
self.change(A, v, mid + 1, right, root * 2 + 1)
self.update(root)
def query(self, A, B, left, right, root):
if A <= left <= right <= B:
return self.tree[root]
mid = (left + right) // 2
res = 0
if A <= mid:
res += self.query(A, B, left, mid, root * 2)
if B >= mid + 1:
res += self.query(A, B, mid + 1, right, root * 2 + 1)
return res
def get_ranks(nums):
new_nums = sorted(list(set(nums)))
hp = {v: r + 1 for r, v in enumerate(new_nums)}
return hp
hp = get_ranks(a)
new_a = [0] * len(hp)
tree = segment_tree(new_a)
tree.build(1, len(hp), 1)
ans = 0
for i in a:
p = hp[i]
if p + 1 <= len(hp):
ans += tree.query(p + 1, len(hp), 1, len(hp), 1)
temp = tree.query(p, p, 1, len(hp), 1)
tree.change(p, temp + 1, 1, len(hp), 1)
return ans
树状数组：
class Solution:
def reversePairs(self, record: List[int]) -> int:
a = record
class binary_indexed_tree:
def __init__(self, nums):
self.n = len(nums)
self.nums = nums
self.tree = [0] * (self.n + 1)
def lowbit(self, x):
return x & -x
def change(self, pos, v):
while pos <= self.n:
self.tree[pos] += v
pos += self.lowbit(pos)
def query(self, pos):
res = 0
while pos > 0:
res += self.tree[pos]
pos -= self.lowbit(pos)
return res
def get_ranks(nums):
new_nums = sorted(list(set(nums)))
hp = {v: r + 1 for r, v in enumerate(new_nums)}
return hp
hp = get_ranks(a)
new_a = [0] * len(hp)
tree = binary_indexed_tree(new_a)
ans = 0
for i in a:
p = hp[i]
ans += tree.query(len(hp)) - tree.query(p)
temp = tree.query(p) - tree.query(p - 1)
tree.change(p, 1)
return ans
树状数组单点查询还有优化的写法，暂且不表，按前缀和处理比较容易懂