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