Luogu P1908 逆序对

思路

关于逆序对，我们就需要先介绍一下它的定义：在数组\(a\)中，若\(a [ i ] > a [ j ]\) 且$ i < j$，那么我们就称 \(a [ i ]\) 和 \(a [ j ]\) 是一对逆序对。了解了逆序对的定义，我们很容易就可以想出

逆序对的一种暴力求法：遍历整个数组，找到符合定义的数对并统计数量。但是这样做的话，\(O（N^2）\)的复杂度会让你痛不欲生。所以我们就有了两种高效的解法：归并排序做法和树状数组做法（线段树

做法与树状数组类似）。

由于最近在练习树状数组，所以这里介绍一下树状数组解法（线段树解法和树状数组解法类似）。那问题是，我们要用树状数组怎样统计某个数和它之前的数能够成多少个逆序对呢？

我们可以考虑根据数组中每个数的值来建立树状数组。开始时树状数组的值全部为\(0\)，然后按照数据从左到右的顺序依次将每个数对应的位置加\(1\)，代表有这样一个数。而这样做再循环到第i项的时候，前

\(i-1\)项已经被加入树状数组中了，而根据逆序对的定义，在树状数组内（注意一定是在树状数组内！）比当前数大的都会与\(a [ i ]\) 构成逆序对（因为我们是从左到右依次加入的，所以树状数组内的所

有数出现的都比\(a [ i ]\)早）。因此，产生的逆序对的数量即为 \(i - query( i )\)。那么这样就可以了吗？

其实不然。我们观察给定数列中的值的最大为\(109\)，而如果我们开一个大小为\(109\)的\(int\)类型的数组，那空间一定会爆炸。而根据题目的特殊性，我们只需要知道每个数之间的大小关系，而并不需要知道

某个数具体是几。这样我们就需要一个叫做离散化的东西。我们将原数组排序 ，记录下每一个数在原数组中的位置，用\(1—n\)分别对应\(n\)个数表示它们的相对大小，这样开一个树状数组的空间就足够了。我

们做了这么多，那这样就可以AC了吗？

事实证明，就算我们做了这么多，还是不够。有一个问题需要我们严肃对待：那就是原数组中的相等元素。对于每一个数，它离散化之后所对应的新数都是不同的。如果我们不做处理，那么有与\(a\)相等的元

素在\(a\)之后加入且后加入的这个数离散化之后相对大小比\(a\)要大，就会出现把两个相等的数判断为逆序对的情况。这个问题要很好解决。我们只需要在排序的时候将元素的值作为第一关键字、把元素的编号

作为第二关键字进行排序，这样的话两个相等的数中编号小的相对大小也就会更小，就不会出现把两个相等的数判断为逆序对的情况。

最后，唯一需要注意的事就是统计答案的变量要开\(long long\)！

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define MAXN 500005
#define lowbit(x) x&(-x)
typedef long long ll;
int n,tree[MAXN];
int rank[MAXN];
struct node{
	int val,pos;
}a[MAXN];
ll ans=0;
inline void Insert(int x,int k){
	for(;x<=n;x+=lowbit(x))
		tree[x]+=k;
	return;
}
inline ll Query(int x){
	ll res=0;
	for(;x;x-=lowbit(x))
		res+=tree[x];
	return res;
}
inline int cmp(node a,node b){
	if(a.val!=b.val)return a.val<b.val;
	else return a.pos<b.pos;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i].val),a[i].pos=i;
	std::sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;++i)
		rank[a[i].pos]=i;
	for(int i=1;i<=n;++i)
		Insert(rank[i],1),ans+=i-Query(rank[i]);
	printf("%lld\n",ans);
	return 0;
}

Luogu P1908 逆序对

原文：https://www.cnblogs.com/ShadowFlowhyc/p/13380791.html