树状数组之逆序对,第二种离散化(sort映射)
一个序列对另一个序列进行sort映射时,要判重,否则sort会出现玄学乱排
sort映射:见代码吧
此题求的是逆序对 b对a进行sort映射后,其相对位置不变,所以可以把此种方式看作离散化的一种
a变成升序的交换次数=升序变成a的交换次数 b映射后,其相对位置对a来说是升序
逆序对: a是位置升序,所以只要求后面的元素是否比前面的小 b是元素升序,所以只要求后面元素的位置是否比前面的小 即之前求的是元素逆序,现在求的是位置逆序
//以后就用这种离散化了,不用它
sort映射一般用在两个数组都是排列数的情况,或者使用方是排列数, 因为比如a不是排列数的情况下,a映射到b中可能越界
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define low(x) x&(-x)
int const N=5e5+7;
int n;
ll tr[N],a[N],b[N]; //b是离散化后的数组,b[i]也可以看成一个位置,即第i小的数在a数组中的位置 //b就是a升序后a元素的位置,所以b中的逆序对(例逆序对x和y),表示a排完序后y在x前且y比x大
void add(int p,int w){
for(;p<=n;p+=low(p)){
tr[p]+=w;
}
}
ll ask(int p){
ll res=0;
for(;p;p-=low(p)){
res+=tr[p];
}
return res;
}
bool cmp(int i,int j){ //return a[ b[i] ] < a[ b[j] ];
return a[i]!=a[j]?a[i]<a[j]:i<j;
}
int main(){
cin >> n;
ll ans=0;
for(int i=1;i<=n;++i){
cin >> a[i];b[i]=i;
}
sort(b+1,b+n+1,cmp); //b对a进行sort映射
for(int i=1;i<=n;++i){
add(b[i],1);
ans+=i-ask(b[i]);
}
cout << ans;
return 0;
}
线段树和数状数组经典例题 文章被收录于专栏
线段树和数状数组经典例题