逆序对2

我什么时候说的我去

不管了给一发离散化+树状数组题解好了

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+25;
ll n,cnt,ans;
ll a[MAXN],b[MAXN],tree[MAXN];
inline ll lowbit(ll x){return x&-x;}
inline void update(ll idx,ll c){
	for(ll i=idx;i<=n;i+=lowbit(i)) tree[i]+=c;
	return;
}
inline ll query(ll idx){
	ll res=0;
	for(ll i=idx;i>=1;i-=lowbit(i)) res+=tree[i];
	return res;
}
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	cnt=unique(b+1,b+1+n)-b-1;
	for(ll i=1;i<=n;i++){
		a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
		ans+=query(n)-query(a[i]);
		update(a[i],1);
	}
	cout<<ans;
	return 0;
}