AcWing 788. 逆序对的数量

题目连接

https://www.acwing.com/problem/content/790/

思路

归并排序求逆序对是一个很经典的利用归并排序的特性的一个题目，上一篇博客讲到了归并排序的其实就是我们划分出来 l o g 2 n log_2n log2​n层交换层，每下一层的划分都是划分当前这一层的一半如图 大概是这个图的形式，所以我们是先递归最终递归到区间长度2or1，然后再处理区间，对于我们处理的这个区间，我们又划分成了两段，在这两段我们通过双指针的算法可以实现 O ( N ) O(N) O(N)的时间复杂度有序的合并，在合并的时候，如果指针i之后的数都大于当前的j，所以加上这个区间，由于是在归的过程中操作的所以不会重复计算，详情请看代码

代码

#include
using namespace std;
#define ll long long
ll ans;
const int N = 1e5+10;
int a[N],temp[N];

void merge_sort(int l,int r) {
	if(l >= r) return;
	int mid = l + r >> 1;
	merge_sort(l,mid);
	merge_sort(mid+1,r);
	int i = l,j = mid + 1,k = 0;
	while(i