树状数组之逆序对,第二种离散化(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;
}

线段树和数状数组经典例题 文章被收录于专栏

线段树和数状数组经典例题

全部评论

相关推荐

点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务