#题解逆序对

我们先来读题

题目描述

猫猫 $TOM$ 和小老鼠 $JERRY$ 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。
最近， $TOM$ 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。
$Update:数据已加强$

输入格式

第一行，一个数 $nn$ ，表示序列中有 $nn$ 个数。
第二行 $nn$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$ 。

输出格式

输出序列中逆序对的数目。

输入输出样例

输入 #1

6
5 4 2 6 3 1

输出 #1

说明/提示

对于 25% 的数据， $n≤2500$

对于 50% 的数据， $n≤4×10^4$

对于所有数据， $n≤5×10^5$
$请使用较快的输入输出应该不会 O(n^2)过 50 万吧 by chen\_zhe$

具体实现

在我们讲解这道题之前，先来了解一个排序算法——归并排序，这一次我们就要利用归并排序解题。归并排序的核心是对有序数组的合并，在合并过程中，就有 $i$ 和 $j$ 而 $i$ 的值是 $l$ ~ $mid$ , $j$ 的值是 $mid$ +1~ $r$ ,所以他们就构成了天然有序的 $i$ 和 $j$ ，接下来，只需要找到 $a$ _i > $a$ _j,而在 $a$ _i > $a$ _j时， $a$ _i+1 > $a$ _j， $a$ _i+2 > $a$ _j……一直到 $a$ _mid > $a$ _j，此时就有了 $mid-i+1$ 个逆序对，加到统计变量中即可。

归并排序完整代码

int a[1000000],t[1000000];
void merge(int l,int mid,int r){
	//l~mid
	//mid+1 ~r 
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(a[i]>a[j]){
			t[k++]=a[j++];
		}else{
			t[k++]=a[i++];
		}
	}
	while(i<=mid) t[k++]=a[i++];
	while(j<=r) t[k++]=a[j++];
	// t[l~r]  
	for(int x=l;x<=r;x++){
		a[x]=t[x];
	}
	
}

void mergeSort(int l,int r){
  if(l>=r) return ; 
  int mid =(l+r)/2;
  //1. 左右两边有序
  mergeSort(l,mid);
  mergeSort(mid+1,r);
  //O（n） 合并
  merge(l,mid,r);
}

先加上一个变量sumlong long sum=0;~~不要问我干嘛用long long，自己试去~~
接下来找到判断大小的那一段。

	while(i<=mid&&j<=r){
		if(a[i]>a[j]){
			t[k++]=a[j++];
		}else{
			t[k++]=a[i++];
		}
	}

在t[k++]=a[j++]; 后面加上 sum+=mid-i+1;就变成了……

	while(i<=mid&&j<=r){
		if(a[i]>a[j]){
			t[k++]=a[j++];
            sum+=mid-i+1;
		}else{
			t[k++]=a[i++];
		}
	}

———————————————————————————————————————————————
至此函数的改变都改好了~~是不是很简单？~~
我们再来把输入输出和函数调用完善一下。
主函数代码：

int main(){
	//freopen("1.in","w",stdin);定义输入文件，这个语句执行一次后，一定要注释掉，不然你会疯的
	//freopen("1.in","r",stdin);读取输入文件
	//freopen("1.out","w",stdout);这些比赛时才用得着，了解一下吧
	//**********文件**************
	
	long n=0;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
    mergeSort(0,n-1);
	cout << sum;
	
	return 0;//养成良好的习惯 
}

完整代码

#include<bits/stdc++.h>//万能头文件 
using namespace std;
int a[500010],t[500010],n;
long long sum=0;
void merge(int l,int mid,int r){
	//l~mid
	//mid+1 ~r 
    
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(a[i]>a[j]){
			t[k++]=a[j++];
            sum+=mid-i+1;
		}else{
			t[k++]=a[i++];
		}
	}
	while(i<=mid) t[k++]=a[i++];
	while(j<=r) t[k++]=a[j++];
	// t[l~r]  
	for(int x=l;x<=r;x++){
		a[x]=t[x];
	}
	
}
void mergeSort(int l,int r){
  if(l>=r) return ; 
  int mid =(l+r)/2;
  mergeSort(l,mid);
  mergeSort(mid+1,r);
  merge(l,mid,r);
}

int main(){
	//freopen("1.in","w",stdin);定义输入文件，这个语句执行一次后，一定要注释掉，不然你会疯的
	//freopen("1.in","r",stdin);读取输入文件
	//freopen("1.out","w",stdout);这些比赛时才用得着，了解一下吧
	//**********文件**************
	
	long n=0;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
    mergeSort(0,n-1);
	cout << sum;
	
	return 0;//养成良好的习惯 
}

有兴趣的小伙伴可以自己做完后在洛谷提交通道提交哦。

我的第一次提交代码

#include<bits/stdc++.h>//万能头文件 
using namespace std;
int a[500010],t[500010],n,sum=0;
void merge(int l,int mid,int r){
	//l~mid
	//mid+1 ~r 
    
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(a[i]>a[j]){
			t[k++]=a[j++];
            sum+=mid-i+1;
		}else{
			t[k++]=a[i++];
		}
	}
	while(i<=mid) t[k++]=a[i++];
	while(j<=r) t[k++]=a[j++];
	// t[l~r]  
	for(int x=l;x<=r;x++){
		a[x]=t[x];
	}
	
}
void mergeSort(int l,int r){
  if(l>=r) return ; 
  int mid =(l+r)/2;
  mergeSort(l,mid);
  mergeSort(mid+1,r);
  merge(l,mid,r);
}

int main(){
	//freopen("1.in","w",stdin);定义输入文件，这个语句执行一次后，一定要注释掉，不然你会疯的
	//freopen("1.in","r",stdin);读取输入文件
	//freopen("1.out","w",stdout);这些比赛时才用得着，了解一下吧
	//**********文件**************
	
	long n=0;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
    mergeSort(0,n-1);
	cout << sum;
	
	return 0;//养成良好的习惯 
}

估计你是一行一行对才能找到，这也是为什么让你们用 $long long$ 类型
int a[500010],t[500010],n,sum=0;
^ ^
我用的是 $int$ 类型发现没有？所以就过不了。数据类型坑死人呐[大哭]，做题时一定要仔细读题，数据范围也别漏，才能一次通过，取得 $AC$ 。加油(ง •_•)ง

#题解 逆序对