题目描述

一天，小马Pony和Rarity比赛算数。他们要求给定序列的中所包含的逆序对个数，请你设计程序帮助Rarity在比赛中胜过Pony。

逆序对，设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 这个有序对称为 A 的一个逆序对，也称作逆序数。
注意序列中可能有重复数字

输入格式

第一行，一个数 n，表示序列中有 n个数。
第二行，以空格分隔的 n个数，表示给定的序列。序列中每个数字不超过 10^9。

输出格式

一个数，序列中逆序对的数目 m。

输入输出样例

输入1

6
5 4 2 6 3 1

输出1

11

说明

对于 80% 的数据，n≤2000
对于 100% 的数据，n≤10^4。

样例程序：

  1. ans = 0
  2. a = []
  4. def mergeSort(ls):
  5.     if len(ls) < 2:
  6.         return
  7.     mid = len(ls) // 2
  8.     ls1 = ls[0:mid]
  9.     ls2 = ls[mid:len(ls)+1]
  10.     mergeSort(ls1)
  11.     mergeSort(ls2)
  12.     merge(ls1, ls2, ls)
  14. def merge(ls1, ls2, ls):
  15.     i = j = 0
  16.     while i + j < len(ls):
  17.         if j == len(ls2) or (i < len(ls1) and ls1[i] <= ls2[j]):
  18.             ls[i+j] = ls1[i]
  19.             i += 1
  20.             global ans
  21.             ans += j
  22.         else:
  23.             ls[i+j] = ls2[j]
  24.             j += 1
  26. n = int(input())
  27. a = list(map(int, input().split()))
  28. mergeSort(a)
  29. print(ans)

（本题目由武汉理工大学信息1802班 赵中雨 同学贡献，表示感谢！）