1311：【例2.5】求逆序对
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目。
【输入】
第一行为n,表示序列长度，接下来的n行，第n+1行表示序列中的第n个数。
【输出】
所有逆序对总数。
【输入样例】
4
3
2
3
2
【输出样例】
3
【提示】
N≤10^5，Ai≤10^5。
【来源】
No
1. #include <iostream> 2. using namespace std; 3. long long a[100001]; 4. long long r[100001]; 5. long long ans=0; 6. void msort(long long s,long long t){ 7. if(s==t) return; 8. long long mid=(s+t)/2; 9. msort(s,mid); 10. msort(mid+1,t); 11. long long i=s,j=mid+1,k=s; 12. while(i<=mid && j<=t){ 13. if(a[i]<=a[j]){ 14. r[k]=a[i];k++;i++; 15. } 16. else{ 17. r[k]=a[j];k++;j++; 18. ans+=mid-i+1; 19. } 20. } 21. while(i<=mid) { 22. r[k]=a[i];k++;i++; 23. } 24. while(j<=t){ 25. r[k]=a[j];k++;j++; 26. } 27. for(i=s;i<=t;i++) a[i]=r[i]; 28. } 29. int main(int argc,char* argv[]) 30. { 31. long long n,i; 32. cin>>n; 33. for(i=0;i<n;i++) cin>>a[i]; 34. msort(0,n-1); 35. cout<<ans<<endl; 36. return 0; 37. }
