【问题描述】
什么是逆序对？大家自行百度了解下。
接下来我们将会提供一个数字序列，这个序列用空格隔开。
请你从序列第一个元素开始，对每一个元素给出目前为止序列的逆序对数量。
【输入形式】
一行数字，以空格隔开每个数字的元素，回车结束输入。
【输出形式】
若这个序列为 a ，则输出 len(a) 行数据。
第 i 行表示，这个序列到第 i 个元素时，逆序对个数为多少。
【样例输入】
2 4 3 1
【样例输出】
0
0
1
4
def merge_sort(arr, count):
n = len(arr)
if n == 1:
return arr, count
mid = n // 2
left, count = merge_sort(arr[:mid], count)
right, count = merge_sort(arr[mid:], count)
arr_sorted = []
i = 0
j = 0
while i < len(left) or j < len(right):
if i == len(left):
arr_sorted.append(right[j])
j += 1
elif j == len(right):
arr_sorted.append(left[i])
i += 1
elif left[i] <= right[j]:
arr_sorted.append(left[i])
i += 1
else:
arr_sorted.append(right[j])
count += len(left) - i
j += 1
arr = arr_sorted
return arr, count
def inversion_pairs(arr):
count = 0
result = []
for i in range(len(arr)):
slice_arr = arr[: i + 1]
_, c = merge_sort(slice_arr, count)
result.append(c)
count = c
return result
input_arr = list(map(int, input().split()))
result = inversion_pairs(input_arr)
for r in result:
print(r)
glossary = {
'string': 'A series of characters.',
'comment': 'A note in a program that the Python interpreter ignores.',
'list': 'A collection of items in a particular order.',
'loop': 'Work through a collection of items, one at a time.',
'dictionary': "A collection of key-value pairs.",
}
word = 'string'
print("\n" + word.title() + ": " + glossary[word])
word = 'comment'
print("\n" + word.title() + ": " + glossary[word])
word = 'list'
print("\n" + word.title() + ": " + glossary[word])
word = 'loop'
print("\n" + word.title() + ": " + glossary[word])
word = 'dictionary'
print("\n" + word.title() + ": " + glossary[word])