wikioi 1688 求逆序对

/*===========================================================
wikioi 
1688 求逆序对 

时间限制: 1 s    空间限制: 128000 KB

题目描述 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

注解：
    题目考察分治法。解决该题需要用到二路归并排序。 
    假如本题直接使用两重for循环来模拟，则最后肯定是会超时的。
    模拟的Pascal代码如下：
    ans:=0;
    read(n);
    for i:=1 to n do read(a[i]);
    for i:=1 to n-1 do
        for j:=i+1 to n do
            if a[i]>a[j] then ans:=ans+1;
    writeln(ans); 
    这个模拟算法是O(n^2)的算法，所以无法解决N<=10^5这样规模的问题。 
    其实从这个模拟的过程来看，终归是要把序列当中的所有数做两两比较。
    联想到冒泡之类的排序也是要比较的。所以，随便找一个排序算法稍作修改， 
    应该就可以解决问题了。但是，冒泡、选择和直接插入排序都是O(n^2)算法。
    这样的算法并未能提高程序的效率。相反，浪费脑细胞去修改算法。 
    排序算法里面的二路归并排序倒是不错的选择，因为它的时间复杂度是O（n*lg（n））。 
=============================================================*/

 1 #include <stdio.h>
 2 
 3 int n,a[1000100],t[1000010];
 4 long long count=0;
 5 
 6 void merge_sort(int *a,int x,int y,int *t);//对a[]在[x，y) 下标范围的元素进行归并排序 
 7 
 8 int main(int argc, char *argv[])
 9 {
10     scanf("%d",&n);
11     for(int i=0;i<n;i++) scanf("%d",&a[i]);
12     merge_sort(a,0,n,t);
13     printf("%lld\n",count);
14     return 0;
15 }
16 void merge_sort(int *a,int x,int y,int *t)//对a[]在[x，y) 下标范围的元素进行归并排序 
17 {
18     if(y-x>1)
19     {
20         int m=x+(y-x)/2;
21         int p=x,q=m,i=x;
22         merge_sort(a,x,m,t);
23         merge_sort(a,m,y,t);
24         while(p<m||q<y)
25         {
26             if( q>=y || (p<m&&a[p]<=a[q]) ) t[i++]=a[p++];
27             else { t[i++]=a[q++]; count=count+m-p; }
28         }
29         for(i=x;i<y;i++) a[i]=t[i];
30     }
31 }