【学习笔记】逆序对

介绍

逆序对是在数组$a$中能满足$a_i>a_j$且$i<j(1 \leq i \leq n)$的数对。

主要的求法有归并排序求逆序对。

题目

归并排序求逆序对

在归并排序的过程中对逆序对进行求解

//归并排序求逆序对
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=5e5+10;
int n,a[MAXN],tmp[MAXN],ans;
void merge(int l1,int r1,int l2,int r2,int *tmp)
{
	int i=l1,j=l2,idx=l1;
	while(i<=r1 && j<=r2)
		if(a[i]>a[j])
		{
			tmp[idx++]=a[j++];
			ans+=r1-i+1;
		}
		else tmp[idx++]=a[i++];
	while(i<=r1)tmp[idx++]=a[i++];
	while(j<=r2)tmp[idx++]=a[j++];
	for(int p=l1;p<=r2;p++)a[p]=tmp[p];
}
void merge_sort(int l,int r)
{
	//当l==r，[l,r]有序
	if(l==r)return ;
	int mid=l+((r-l)>>1);
	merge_sort(l,mid),merge_sort(mid+1,r);
	merge(l,mid,mid+1,r,tmp);
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	merge_sort(1,n);
	cout<<ans;
	return 0;
}

树状数组求逆序对

树状数组中记录有多少个值为$\text{val}$的数。

离散化之后，从后开始遍历。

在处理$i$时,$j(i<j)$必定已经在树状数组中了，直接$\text{query(a[i]-1)}$，就能知道$a_j<a_i$的个数了

//树状数组求逆序对
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=5e5+10;
int n,a[MAXN],b[MAXN];
int lowbit(int i)
{
	return i& -i;
}
struct fenwick
{
	int t[MAXN];
	void init(){memset(t,0,sizeof(t));}
	void add(int val,bool flag)
	{
		//flag=1 加
		//flag=0 减
		while(val<=n)
			t[val]+=flag,val+=lowbit(val);
	}
	int query(int val)
	{
		//查询有多少比val小的数	
		int ret=0;
		while(val>0)
			ret+=t[val],val-=lowbit(val);
		return ret;
	}
}t;
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
	sort(b+1,b+1+n,less<int>());
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+1+n,a[i])-b;
	int ans=0;
	for(int i=n;i>0;i--)
		ans+=t.query(a[i]-1),t.add(a[i],1);
	cout<<ans;
	return 0;
}