/*===========================================================
wikioi
1688 求逆序对 时间限制: 1 s 空间限制: 128000 KB 题目描述 Description
给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目.
数据范围：N<=105。Ai<=105。时间限制为1s。 输入描述 Input Description
第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。
输出描述 Output Description
所有逆序对总数.
样例输入 Sample Input
4
3
2
3
2
样例输出 Sample Output
3 注解：
题目考察分治法。解决该题需要用到二路归并排序。
假如本题直接使用两重for循环来模拟，则最后肯定是会超时的。
模拟的Pascal代码如下：
ans:=0;
read(n);
for i:=1 to n do read(a[i]);
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then ans:=ans+1;
writeln(ans);
这个模拟算法是O(n^2)的算法，所以无法解决N<=10^5这样规模的问题。
其实从这个模拟的过程来看，终归是要把序列当中的所有数做两两比较。
联想到冒泡之类的排序也是要比较的。所以，随便找一个排序算法稍作修改，
应该就可以解决问题了。但是，冒泡、选择和直接插入排序都是O(n^2)算法。
这样的算法并未能提高程序的效率。相反，浪费脑细胞去修改算法。
排序算法里面的二路归并排序倒是不错的选择，因为它的时间复杂度是O（n*lg（n））。
=============================================================*/
#include<stdio.h> int n,a[],t[];
long long ans=; void merge_sort(int A[],int l,int r,int T[])
{
if(l<r)
{
int m=l+((r-l)>>);
int x=l,y=m+,i=l;
merge_sort(A,l,m,T);
merge_sort(A,m+,r,T);
while(x<=m||y<=r)
{
if(y>r || (x<=m && A[x] <= A[y])) T[i++]=A[x++];
else {T[i++]=A[y++];ans+=(m-x+);}
}
for(i=l;i<=r;i++) A[i]=T[i];
}
} int main()
{ scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
merge_sort(a,,n,t);
printf("%lld\n",ans);
return ;
}
另一段代码：
#include <stdio.h> int n,a[],t[];
long long count=; void merge_sort(int *a,int x,int y,int *t);//对a[]在[x，y) 下标范围的元素进行归并排序 int main(int argc, char *argv[])
{
scanf("%d",&n);
for(int i=;i<n;i++) scanf("%d",&a[i]);
merge_sort(a,,n,t);
printf("%lld\n",count);
return ;
}
void merge_sort(int *a,int x,int y,int *t)//对a[]在[x，y) 下标范围的元素进行归并排序
{
if(y-x>)
{
int m=x+(y-x)/;
int p=x,q=m,i=x;
merge_sort(a,x,m,t);
merge_sort(a,m,y,t);
while(p<m||q<y)
{
if( q>=y || (p<m&&a[p]<=a[q]) ) t[i++]=a[p++];
else { t[i++]=a[q++]; count=count+m-p; }
}
for(i=x;i<y;i++) a[i]=t[i];
}
}
注意：在统计逆序对数目的时候，不要重复统计。