总时间限制: 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

显然，如果单纯的使用双重循环的话，会超出时间限制。
所以这里采用分而治之的方法，分成前后两部分，那么逆序数的个数就是前一部分的逆序数和后一部分的逆序数再加上前一部分整体相对于后一部分的逆序数。显然前两项可以递归调用。
对于第三部分整体的逆序数，我们可以先排序，然后一重循环即可以解决这个问题，最后的算法复杂度是nlogn，而不是n2.
代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
int N;
//注意这里的输出值很大，所以函数返回类型要用long long 而不是int，否则通过不了
long long fun(int f0[], int f1[],int s0,int s1)
{long long temp = 0;sort(f0, f0 + s0);//注意这里一定不能把s0写成s0-1，s0表示要排序s0个数sort(f1, f1 + s1);int i = s0 - 1,j=s1-1;while(i>=0&&j>=0){if (f0[i] <= f1[j]){--j;++i;}else{temp += j;temp++;}--i;}return temp;
}
long long nixu(int x[],int q)
{if (q == 1)return 0;if (q == 2 && x[0] > x[1])return 1;if (q == 2 && x[0] <= x[1])return 0;if (q >= 3){int* p1 = new int[q/2+1];int* p2 = new int[q/2+1];for (int i = 0;i < q / 2;i++)p1[i] = x[i];int d = 0;for (int i = q / 2;i < q;i++){p2[d] = x[i];d++;}return nixu(p1, q / 2) + nixu(p2, q - q / 2) + fun(p1, p2, q / 2, q - q / 2);delete []p1;delete []p2;}
}
int main()
{cin >> N;int* a = new int[N];for (int i = 0;i < N;i++)cin >> a[i];long long sum = nixu(a,N);cout << sum;delete []a;
}