【题解】洛谷P1908逆序对

发布于 2019-09-29  703 次阅读


题目地址

当然讲的不是归并排序


Q1: 我们需要知道,怎么统计第 i 个数会与第1~i−1个数构成多少个逆序对呢?

Ans1: 考虑根据值来建树状数组,初始树状数组为全0。现在按照序列从左到右将数据的值对应的位置的数加一,代表又有一个数出现。因此,在循环到第 i 项时,前 i−1 项已经加入到树状数组内了,树状数组内比 ai 大的都会与 ai 构成逆序对,因为它们一定出现的更早,所以产生的逆序对数量为i-qurry(ai)

注:query(ai)代表在树状数组内询问1 ~ ai项的前缀和


Q2: 根据 ai来建树状数组空间不够啊?

Ans2: 确实不够。但是我们需要的只是数据之间的相对大小,只需要满足大于或小于本身,与大多少无关,具体来说,举个栗子:

//  1 2 10000
//  1 2 3
//上面两个序列在本题是等效的,因为无论第三项是3还是10000,它都大于第一项和第二项

因此需要离散化,先将数据排序,再用 1~n 分别对应 n 个数表示它们的相对大小,对新的序列建树状数组空间就够了


Q3: 相等的元素是否会导致求解错误?每一个数(不管是否相等)对应的新数都不同诶?

Ans3: 不处理的话会出错的,问题的关键在于是否有与 ai 相等的元素在 ai 前被加入且其相对大小标记更大。出现这种情况就会误将两个相等的数判为逆序对。怎么解决呢,只要所有与 ai 相等的元素中,先出现的标记也更小就好了(我们只统计相对更大的)。具体只需要在排序时将 ai 作为第一关键字,下标(第几个出现)作为第二关键字从小到大排序即可。


时间复杂度:$latex O(N log^2N)$

注:时间复杂度瓶颈在排序离散化时


代码如下:

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#define N 500001
#define int long long//注意要用高精度

using namespace std;

int n,tree[N],ans,r[N];

struct node
{
	int val,num;
}a[N];

bool cmp(node x,node y)
{
	if (x.val==y.val) return x.num<y.num;
	return x.val<y.val;
}

int lb(int x)
{
	return x & -x;
}

void add(int x,int k)
{
	for(int i=x;i<=n;i+=lb(i))
		tree[i]+=k;
}

int find(int x)
{
	int sum=0;
	for(int i=x;i;i-=lb(i))
		sum+=tree[i];
	return sum;
}

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].val;
		a[i].num=i;
	}
	sort(a+1,a+n+1,cmp);
	for (int i=1;i<=n;i++)
		r[a[i].num]=i;//离散化 
	for(int i=1;i<=n;i++)
	{
		add(r[i],1);
		ans+=i-find(r[i]);
	}
	cout<<ans<<endl;
	return 0;
}

I laid my burdens down, now I'm traveling light.
I found my freedom now, and I'm traveling light.