求排列的逆序数（分治）
一、题目描述
总时间限制:
1000ms
内存限制:
65536kB
描述
在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。
对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，满足 j < k 且 ij > ik， 那么就称(ij,ik)是这个排列的一个逆序。
一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由1,2,…,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。
现给定1,2,…,n的一个排列，求它的逆序数。
输入
第一行是一个整数n，表示该排列有n个数（n <= 100000)。
第二行是n个不同的正整数，之间以空格隔开，表示该排列。
输出
输出该排列的逆序数。
样例输入
6
2 6 3 4 5 1
样例输出
8
提示
1. 利用二分归并排序算法（分治）；
2. 注意结果可能超过int的范围，需要用long long存储。
开始没有思路，我做的题目是没有提示的，这个题目是上网粘贴的，有提示.我开始是没有想到归并排序
有这样一个题 1 4 3 2这四个数，每次交换相邻的两个需要交换几次才能从小到大排序？先2--3交换，再2--4交换
这是因为4比2大且在2的前面，这就相当于是逆序对。
这道题 需要在归并排序的时候统计逆序对的个数。
来自 <https://www.cnblogs.com/zzyh/p/6625872.html>
分析：本题难点在于分析如何用归并法求其逆序数，先来看下逆序数的定义：
某一个数的逆序数等于在它之前有多少个比它大的数
某一个序列的逆序数等于所有数的逆序数之和
序列：9 1 0 5 4
逆序数： 4 + 1 + 1 = 6
了解了逆序数的定义后我们来用归并法进行求解，归并法的具体操作我就不赘述了，就套一个模板即可，写完归并的模板后只需在归并处理两个有序序列合并，且是前指针下标所指元素大于后指针下标所指元素时进行进行一次运算即可，什么运算呢？我们想一下，当前半部分的有序序列的某个元素大于后半部分有序序列的某个元素时，那么自然从前半部分指向的那个元素起到中间下标都是大于后面有序序列的，即比后面元素的逆序数为sum = mid - i + 1（i为前序列的指针下标，mid是中间下标）
如果你听了还是不明白，估计是你归并排序掌握的不牢，可以看看我另一篇关于归并排序的介绍（嘛，虽然说的很水……）
https://blog.csdn.net/Oneplus6/article/details/85888026
#include <iostream>
using namespace std;
const int MAXN = 100005;
long sum = 0;
int temp[MAXN];
void Merge(long num[], long l, long mid, long r)
{
long i = l, j = mid + 1, k = l;
while(i<=mid && j<=r)
{
if(num[i] > num[j])
{
temp[k] = num[j];
k++;j++;
sum += mid - i + 1; //核心代码
}
else
{
temp[k] = num[i];
k++;i++;
}
}
while(i <= mid)
{
temp[k] = num[i];
k++;i++;
}
while(j <= r)
{
temp[k] = num[j];
k++;j++;
}
for(i=l; i<=r; i++)
{
num[i] = temp[i];
}
}
void MergeSort(long num[], long l, long r)
{
if(l >= r)
{
return;
}
long mid = (l+r)/2;
MergeSort(num, l, mid);
MergeSort(num, mid+1, r);
Merge(num, l, mid, r);
}
int main()
{
long n;
long num[MAXN];
cin >> n;
for(int i=0; i<n; i++)
{
cin >> num[i];
}
MergeSort(num, 0, n-1);
cout << sum << endl;
return 0;
}