1019 逆序数

基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题

关注

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。

Input

第1行：N，N为序列的长度（n <= 50000)
第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）

Output

输出逆序数

Input示例

Output示例

相关问题

逆序排列

略是费解.....本以为和poj上的一样,可是代码还是重写啦.....

归并思想:http://blog.csdn.net/morewindows/article/details/6678165

代码:

 1 #include <vector>
 2 #include <map>
 3 #include <set>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cstdio>
 7 #include <cmath>
 8 #include <cstdlib>
 9 #include <string>
10 #include <cstring>
11 #include <queue>
12 #include <stack>
13 using namespace std;
14 
15 const int N=500000+10;
16 
17 int a[N],tep[N],ans;
18 
19 void mor_sort(int l,int r)
20 {
21     int i,j,k,m;
22     m=(l+r)/2;
23     i=l;
24     k=l;
25     j=m+1;
26     while(i<=m && j<=r){
27         if(a[i]>a[j]){
28             tep[k++]=a[j++];
29             ans+=m-i+1;
30         }
31         else{
32             tep[k++]=a[i++];
33         }
34     }
35     while(i<=m)
36         tep[k++]=a[i++];
37     while(j<=r)
38         tep[k++]=a[j++];
39     for(int i=l; i<=r; i++){
40         a[i]=tep[i];
41     }
42 }
43 
44 void solve(int l,int r)
45 {
46     int m;
47     m=(l+r)/2;
48     if(l<r){
49         solve(l,m);
50         solve(m+1,r);
51         mor_sort(l,r);
52     }
53 }
54 
55 int main()
56 {
57     int n;
58     ans=0;
59     scanf("%d",&n);
60     for(int i=1; i<=n; i++){
61         scanf("%d",&a[i]);
62     }
63     solve(1,n);
64     printf("%d
",ans);
65     return 0;
66 }