Table of Contents

SGU180 解题手记
　　求一个序列中的逆序对个数。把序列从中间分开，先统计左右两边的子序列中各自的逆序对个数，然后把左右两边排序，这样就可以统计出左边和右边之间的逆序对的个数。以上过程其实就是MergeSort。
　　Submit 1: WA on 12。仔细检查了程序发现没有逻辑错误。看SGU的forum发现需要注意两点：1.需要用long long；2.输出long long应该用%I64d。
　　Submit 2: AC。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <cstdio>
#include <cstring>
using namespace std;
 
const int MAXN=65537;
int a[MAXN];
 
long long mergesort(int *a,int n)
{
    int l=n>>1,r=n-l,*tmp=new int[n+1],*tmph=tmp;
    long long c=l?mergesort(a,l)+mergesort(a+l,r):0;
    for (int i(0),j(l);i<=l;*(tmp++)=a[i++])
        for (;j<n && (i==l || a[i]>a[j]);*(tmp++)=a[j++],c+=l-i);
    memcpy(a,tmph,n*sizeof(int));
    delete[] tmph;
    return c;
}
 
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=0;i<n;++i) scanf("%d",a+i);
    printf("%I64d\n",mergesort(a,n));
    return 0;
}