http://acm.hdu.edu.cn/showproblem.php?pid=3743
测试模板的一道题，蛮好的。
敲了两种板子，白书上的第一种板子有点问题，改了一下，还是不太理解。
第二种网上的好理解。
#include <iostream>
#include<stdio.h>
#include<cstring>
#include<map>
#include<string.h>
#include<algorithm>
using namespace std;long long cnt=0;
//void merge_sort(int* A,int x,int y,int* T)
//{
// if(y-x>1) //!包括x，不包括y
// {
// int m=x+((y-x)>>1);
// 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++];
// cnt+=abs(m-p);
// }
// }
// for(int i=x;i<y;i++)
// A[i]=T[i];
// }
// else if(A[x]>A[y])
// {
// swap(A[x],A[y]);
// cnt++;
// }
//}void merge_sort(int* A,int x,int y,int* T)
{if(x==y) return;int mid=(x+y)>>1,i,j,k;i=x,k=x,j=mid+1;merge_sort(A,x,mid,T);merge_sort(A,mid+1,y,T);while(i<=mid&&j<=y){if(A[i]<=A[j]) T[k++]=A[i++];else cnt+=mid-i+1,T[k++]=A[j++];}while(i<=mid) T[k++]=A[i++];while(j<=y) T[k++]=A[j++];for(int i=x;i<=y;i++)A[i]=T[i];
}int source[1000008],t[1000008];int main()
{int num;while(scanf("%d",&num)!=EOF){cnt=0;for(int i=0;i<num;i++){scanf("%d",&source[i]);}merge_sort(source,0,num-1,t);printf("%I64d\n",cnt);}return 0;
}