求逆序数_归并排序

求逆序数

时间限制： 2000 ms | 内存限制：65535 KB

难度： 5

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

现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。

比如 1 3 2 的逆序数就是1。

</dd> </dl>

<dl class="others"> <dt> 输入 </dt> <dd> 第一行输入一个整数T表示测试数据的组数（1<=T<=5)
每组测试数据的每一行是一个整数N表示数列***有N个元素（2〈=N〈=1000000）
随后的一行共有N个整数Ai(0<=Ai<1000000000)，表示数列中的所有元素。

数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。 </dd> <dt> 输出 </dt> <dd> 输出该数列的逆序数 </dd> <dt> 样例输入 </dt> <dd>

</dd> <dt> 样例输出 </dt> <dd>

0
1

</dd> <dt> 来源 </dt> <dd> [张云聪]原创 </dd> <dt> 上传者 </dt> <dd> 张云聪 </dd> <dd> 思路：看懂归并排序自然就明白这个了。 </dd> </dl>

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 #define maxxx 1000005
 5 
 6 using namespace std;
 7 
 8 long int a[maxxx],b[maxxx];//b作临时数组
 9 long long int cou;
10 
11 void mergee(long int a[],int start,int mid,int endd){
12     int i=start,j=mid+1;
13     int k=start;
14     while(i<=mid&&j<=endd){
15         if(a[i]<=a[j]){
16             b[k++]=a[i++];
17         }else{
18             cou+=j-k;
19             b[k++]=a[j++];
20         }
21     }
22     while(i<=mid){
23         b[k++]=a[i++];
24     }
25     while(j<=endd){
26         b[k++]=a[j++];
27     }
28     for(int i=start;i<=endd;i++){
29         a[i]=b[i];
30     }
31 }
32 
33 void mergesort(long int a[],int start,int endd){
34     if(start<endd){
35         int mid=(start+endd)/2;
36         mergesort(a,start,mid);
37         mergesort(a,mid+1,endd);
38         mergee(a,start,mid,endd);
39     }
40 }
41 
42 int main()
43 {
44     int t;
45     int n;
46     scanf("%d",&t);
47     for(int j=0;j<t;j++){
48         cou=0;
49         scanf("%d",&n);
50             for(int i=0;i<n;i++){
51             scanf("%d",a+i);
52         }
53         mergesort(a,0,n-1);
54         printf("%lld\n",cou);
55     }
56     return 0;
57 }