题目：
小易给定一个1到n的排列，希望你能求出这个序列中所有逆序对的距离和。
下标i,j的距离为|i-j|，逆序对是指序列中一对下标i,j满足i<j且ai>aj.
输入描述:
第一行数字n表示排列长度
接下来一行n个数字表示这个排列
1≤n≤100000
输出描述:
一行一个数字表示答案
输入例子1:
5
1 3 4 2 5
输出例子1:
3
例子说明1:
逆序对:
(3, 2)距离为2
(4, 2)距离为1
总和为3
参考：
思路：归并排序的同时记录和，直接暴力法不可取，复杂度过高
n = int(input()) nums = list(map(int, input().split())) ans = 0 def mergesort(l): global ans L = len(l) if L <= 1: return l mid = L // 2 left = mergesort(l[0:mid]) right = mergesort(l[mid:]) res = [] sum_left = sum(left) if left else 0 while left and right: if right[0] < left[0]: ans += sum_left - len(left) * right[0] res.append(right[0]) right.pop(0) else: sum_left -= left[0] res.append(left[0]) left.pop(0) if left: res += left elif right: res += right return res mergesort(nums) print(ans)
原文：https://www.cnblogs.com/ai-learning-blogs/p/13449451.html