题目描述 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
分析：这个是对归并排序的典型应用
1 #include<stdio.h> 2 3 int n,a[1000100],t[1000010]; 4 long long ans=0; 5 6 void merge_sort(int A[],int l,int r,int T[]) 7 { 8 if(l<r) 9 { 10 int m=l+((r-l)>>1); 11 int x=l,y=m+1,i=l; 12 merge_sort(A,l,m,T); 13 merge_sort(A,m+1,r,T); 14 while(x<=m||y<=r) 15 { 16 if(y>r || (x<=m && A[x] <= A[y])) T[i++]=A[x++]; 17 else {T[i++]=A[y++];ans+=(m-x+1);} 18 } 19 for(i=l;i<=r;i++) A[i]=T[i]; 20 } 21 } 22 23 24 int main() 25 { 26 27 scanf("%d",&n); 28 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 29 merge_sort(a,1,n,t); 30 printf("%lld\n",ans); 31 return 0; 32 }
