[算法日常] 逆序对
[算法日常] 逆序对
定义
在一个长度为 \(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++！！！