[算法日常] 逆序对

[算法日常] 逆序对

定义

在一个长度为 \(n\) 的数组 \(a\) 中，若存在 \(\forall 1\le i,j\le n\)，使得 \(a_i>a_j\) ，则称 \(<a_i,a_j>\) 为一对逆序对。

举个例子，一个长度为 \(5\) 的数组为：

1 5 3 6 4

则存在 \(3\) 个逆序对，分别是 \(<5,3>,<5,4>,<6,4>\)。

解法

F1：

显然，可以枚举 \(\forall 1\le i,j\le n\)，若满足 \(a_i>a_j\)，则答案 \(+1\)。

#include<bits/stdc++.h>
using namespace std;
#define ljl long long
const ljl N=5e5+5;
ljl n,a[N],ans;
int main(){
    scanf("%lld",&n);
    for(ljl i=1;i<=n;i++)
        scanf("%lld",&a[i]);
   	for(ljl i=1;i<=n;i++)
        for(ljl j=i+1;j<=n;j++)
            if(a[i]>a[j])
                ++ans;
   	printf("%lld\n",ans);
    return 0;
}

现场手打的代码，没有编译过

F2：重点：利用可维护区间的数据结构

首先再次分析题目。

不难想到，可以记录所有比 \(a_i\) 大的数字个数，最后 \(a_i\)​ 对答案的贡献即为比它大的数字个数。

不妨用 \(bkt_i\) 表示 \(i\) 出现的次数（类似于桶）。

因为是求所有 \(\ge a_i\) 的值，所以就可以将数组排序，然后统计 \(i\sim n\) 的数字个数和。

那么就扯上了区间问题。

那么网上大多数人都是用树状数组来进行区间维护。而我——用线段树！！！！

万能的线段树，接受我的膜拜！！！！！

话说我咋还没有发表过关于线段树的博客啊……最近学业有点忙，待更新！！！

正题。

还有一个问题，就是关于桶。

如果 \(a_i\) 的范围过大？空间肯定爆炸。

这时候，离散化就出场了。

离散化：

对于有些问题，我们仅需要知道其值与其他数字的关联（比如大小排序），就可以将其下标赋值为排序后的排名（奇怪的修辞）。

利用区间数据结构查询区间和

综上所述，可以想到用 \(b\) 表示原数组，\(id_i\) 表示在原数组中第 \(i\) 小的数，最后统计区间 \(a_i\) 的值即可。

例题

洛谷 P1908 逆序对。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ljl long long
#define lc p<<1
#define rc p<<1|1
const ljl N=5e5+5;
ljl n,ans,id[N],b[N];
struct SMT{
	ljl l,r,sum;
}e[N<<4];
void build(ljl l,ljl r,ljl p)//线段树建树
{
	e[p].l=l;e[p].r=r;
	if(l==r)
	{
		e[p].sum=0;
		return;
	}
	ljl mid=l+r>>1;
	build(l,mid,lc);
	build(mid+1,r,rc);
	e[p].sum=e[lc].sum+e[rc].sum;
	return;
}
void add(ljl x,ljl val,ljl p)//遇到了离散化后下标为x的数，将其个数+1
{
	if(e[p].l==e[p].r)
	{
		e[p].sum++;
		return;
	}
	ljl mid=e[p].l+e[p].r>>1;
	if(x<=mid)
		add(x,val,lc);
	if(x>mid)
		add(x,val,rc);
	e[p].sum=e[lc].sum+e[rc].sum;
	return;//与线段树正常的单点修改大同小异
}
ljl query(ljl l,ljl r,ljl p)//查询区间
{
	if(l<=e[p].l&&e[p].r<=r)
		return e[p].sum;
	ljl ans=0,mid=e[p].l+e[p].r>>1;
	if(l<=mid)
		ans+=query(l,r,lc);
	if(r>mid)
		ans+=query(l,r,rc);
	return ans;
}
int main(){
	scanf("%lld",&n);
	for(ljl i=1;i<=n;i++)
	{
		scanf("%lld",&b[i]);//原数组
		id[i]=b[i];//开始先赋值为原数组
	}
	sort(b+1,b+n+1);
	unique(b+1,b+n+1);//去重，是离散化的一个重要部分
	for(ljl i=1;i<=n;i++)
	{
		ljl pos=lower_bound(b+1,b+n+1,id[i])-b;
        //lower_bound：查询区间内第一个大于等于它的元素，因为是二分查找，所以时间是log n。
		id[i]=pos;
	}
	build(1,n,1);
	for(ljl i=1;i<=n;i++)
	{
		ans=ans+query(id[i]+1,n,1);//查询id[i]+1 ~ n 的区间
		add(id[i],1,1);
	}
	printf("%lld\n",ans);
	return 0;
}

预祝大家 CSP-J/S 2024 RP++！！！