题目描述

求逆序对个数

逆序对 设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。比如数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。

输入输出格式

输入格式：

• 第一行 一个数n，表示序列中有n个数。
• 第二行 n个数，表示给定的序列。序列中每个数字不超过10^12

输出格式：

• 给定序列中逆序对的数目。

输入输出样例

输入样例：

6
5 4 2 6 3 1

输出样例：

11

测试点

测试点：5个测试点，每个测试点得20分。

测试限制：每个测试点时间限制1s，内存限制128M。

数据范围：

• 20%：n≤100
• 60%：n≤4×10^4
• 100%：n<=5x10^5
• 1<=所有数据<=5x10^5

分析

1、朴素算法

复杂度o(n^2)，大概能得20分,双重循环即可。

2、归并排序

比如将下面两个区间排序

a_i mid=4 a_j

左3,4,7,9 右1,5,8,10

首先将右区间的 1 取出，放到r_k中，此时 1 是比每个a_i中的元素都小，也就是说此时i的指针指向a_1的位置，此刻得到的逆序对的数量为 4； r_k= 1

然后再将a_i和a_j比较（直到a_i<a_j），a_i<a_j,将a_i的元素放到r_k中； r_k= 1,3,4;

现在a_j>a_i, i 指向a_3的位置，将 5 放到r_k中，得到的逆序对数量为 2 ； r_k= 1,3,4,5

以此类推，直到进行完归并排序，每次合并都会求出逆序对的数目，即mid-i+1,最后每次将ans加上mid-i+1即可得到最后的答案。

细节：被谁淘汰到tr_k时，就根据对方位置来计算。

Thank you very much