逆序数-题解（C++代码） 离散化+树状数组

解题思路:

离散化+树状数组典型应用

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+3;
struct node{
	int v,i;//值，下标 
	bool operator<(const node &o)const{
		return this->v<o.v;
	}
};
node a[N];//初始序列 
int b[N];//序列a离散化后的序列 
int bit[N];
void add(int i,int x){
    while(i<N){
        bit[i]+=x,i+=i&-i;
    }
}
int ask(int i){//已维护序列中<=i的数的个数
    int ans=0;
    while(i){
        ans+=bit[i],i-=i&-i;
    }
    return ans;
}
int main(){
    int n,res=0;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d",&a[i].v);a[i].i=i;
    }
    sort(a,a+n);
    for(int i=0;i<n;++i){
    	b[a[i].i]=i+1;
    }
    for(int i=0;i<n;++i){
        res+=i-ask(b[i]);//前i-1个数中大于b[i]的个数
        add(b[i],1);
    }
    cout<<res;
    return 0;
}