【问题描述】

对于一个长度为N的整数序列A，满足i < j 且 Ai > Aj的数对(i,j)称为整数序列A的一个逆序。

请求出整数序列A的所有逆序对个数。

【输入形式】

输入包含多组测试数据，每组测试数据有两行，

第一行为整数N(1 <= N <= 20000)，当输入0时结束，

第二行为N个整数，表示长为N的整数序列。

【输出形式】

每组数据对应一行，输出逆序对的个数。

【样例输入】

5

1 2 3 4 5

5

5 4 3 2 1

1

1

0

【样例输出】

0

10

0

分析

直接暴力遍历的话，算法复杂度肯定到O ( n 2 ) O(n^2)O(n 2 )

结合分治和归并排序的思想

我们可以将求一个序列的逆序数，转换为求左右两个序列的逆序数相加，同时进行从小到大的排序

而一个序列的逆序数怎么求？因为此序列已经由子序列递归得到，左右序列在各自的内部已经由小到大有序，分别从各自的第一个数开始比较，如果出现第一组的数大于第二组的数，那么第一组后面的数肯定大于第二组此时的数。

举个例子：对于1 , 3 , 4 , 5 , 2 , 6 , 7 , 8 1,3,4,5,2,6,7,81,3,4,5,2,6,7,8，所以1 , 3 , 4 , 5 1,3,4,51,3,4,5是A，2 , 6 , 7 , 8 2,6,7,82,6,7,8是B组，可以看出组内已经有序，

比较1和2，1<2，不统计，A组后移1个数 比较3和2，3>2，所以逆序对+3（第一组后面还有3个数），B组后移1个数 比较3和6，……

Limitation

1s, 1024KiB for each test case.