求逆序对的数量

求逆序对的数量

什么是逆序对

设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。
如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。

使用树状数组求逆序对

在树状数组中，我们维护一个tr数组，这个数组的含义是目前A中的数字出现的次数

我们便可以通过逆序对的query操作和add操作进行动态求解。

因为A的数据可能不是一个标准的排列，所以我们需要离散化一下数据，防止数据过大，

下面使用unordered_map<int,int> S;进行离散化，进行一个值的映射，获取映射值的函数为

auto get(auto x)
{
    if(S.count(x) == 0) S[x] = ++ idx;
    return S[x];
}

我们首先要吧映射值给求一遍，这要求我们的数据是有序的，所以我们需要先进行一次排序获取映射值。

之后动态对tr数组进行add和query,从最后一个往前推，每次答案加上query(y-1),是求在当前已经有的数字，有多少个小于当前数字（正确顺序是大于）。

如果正推，则为query(n) - query(y)。

每次查询完，将当前数字插入tr数组

代码片段

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#define _fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()

using namespace std;
typedef long long LL ;
typedef pair<int,int> PII;
const char nl = '\n';
const int INF = 0x3f3f3f3f;
const int N = 100005;
LL tr[N];
LL a[N],c[N],n,ans,idx;
unordered_map<int,int> S;
LL lowbit(int x)
{
    return x & -x;
}
void add(int x,int v)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i] += v;
}
LL query(int x)
{
    LL res = 0;
    for(int i=x;i;i-=lowbit(i)) res += tr[i];
    return res;
}
LL get(int x)
{
    if(S.count(x) == 0) S[x] = ++ idx;
    return S[x];
}
int main()
{
    cin >> n;
    for(int i=0;i<n;++i) cin >> a[i];
    memcpy(c,a,sizeof a);
    sort(a,a+n);
    for(int i=0;i<n;++i) get(a[i]);
    for(int i=n-1;i>=0;--i)
    {
        int y = get(c[i]);
        ans += query(y-1);
        add(y,1);
    }
    cout << ans << nl;
    return 0;
}

使用归并排序求逆序对

实际上数字的交换次数即为A的逆序对数量
我们分区间来看
一个区间的逆序对数量=左边逆序对的数量+右边逆序对的数量+跨边界的逆序对数量。
和一般的归并排序不同的是res+=mid-i+1,
这里便是跨边界的逆序对的数量,其实就是在归并过程中，如果有的某一个数大于左边的一个数，就把左边遍历到的数字数量加上。因为左边是有序的，只要右边的数小于左边的一个数，就会小于左边那个数及前面所有的数。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
int a[N];
int tmp[N];
int n;

ll merge_sort(int *q,int l,int r)
{
	if(l>=r) return 0;
	int mid = l+r>>1;
	ll res = merge_sort(q,l,mid)+merge_sort(q,mid+1,r);
	int k=0,i=l,j=mid+1;
	while(i<=mid && j<=r)
	{
		if(q[i]<=q[j]) tmp[k++] = q[i++];
		else {tmp[k++] = q[j++];res+=mid-i+1;}	
	}
	while(i<=mid) tmp[k++] = q[i++];
	while(j<=r) tmp[k++] = q[j++];
	for(int i=l,j=0;i<=r;++i,++j) q[i] = tmp[j];
	return res;
}

int main()
{
	cin>>n;
	for(int i=0;
	i<n;++i) cin>>a[i];
	cout<<merge_sort(a,0,n-1);
	return 0;
}

这两种算法求逆序对的时间复杂度理论都为(nlogn),但从代码角度考虑，我更为推荐树状数组解法。