离散化&树状数组求逆序对
#数据结构#算法
Acwing相关题目链接 求逆序对一般有归并排序和树状数组两种方法，这里介绍的是后者，如果数据范围太大，需要对其进行离散化。
相关C++代码如下：
//离散化+树状数组求逆序对
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500005;
ll c[N];
struct node{
ll val,idx;
}a[N];
bool cmp(const node&A,const node&B){
if(A.val!=B.val)return A.val>B.val;
return A.idx>B.idx;
}
int lowbit(int x){
return x&(-x);
}
void add(int i){//i下标++
for(;i<N;i+=lowbit(i))c[i]++;
}
ll sum(int i){
ll s=0;
for(;i;i-=lowbit(i))s+=c[i];
return s;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
while(true){
cin>>n;
if(!n)break;
memset(c,0,sizeof c);
for(int i=1;i<=n;i++){
cin>>a[i].val;
a[i].idx=i;//下标不代表具体的值，但是这个索引是唯一的，对应一个值，从前到后
}
sort(a+1,a+n+1,cmp);//排序规则：1.数值由大到小 2.索引由大到小
//为什么数值由大到小？ 逆序对是每个数前面大于它的个数，从最大的开始遍历，防止漏数
//为什么索引由大到小？ 防止两个数相同多算逆序对
ll ans=0;
for(int i=1;i<=n;i++){
ans+=sum(a[i].idx-1);//索引小的都在它前面
add(a[i].idx);//标记这个索引的值已经存在
}
cout<<ans<<endl;
}
return 0;
}