题解 | A22596.逆序对

本题可以采用 树状数组+离散化 求逆序对

• 离散化

离散化是一种数据处理的技巧，本质上可以看成是一种 哈希，其保证数据在哈希以后仍然保持原来的 全/偏序 关系．

通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照排名来处理问题，即离散化．

用来离散化的可以是大整数、浮点数、字符串等等．

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int n,a[N],tr[N];
vector<int>v;
int lowbit(int x){
    return x & (-x);
}
void add(int x,int c){
    for(int i = x; i <= n; i += lowbit(i)){
        tr[i] += c;
    }
}
int sum(int x){
    long long ans = 0;
    for(int i = x; i >= 1; i -= lowbit(i)){
        ans += tr[i];
    }
    return ans;
}
int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        v.push_back(a[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    long long ans = 0;
    for(int i =n; i>=0; i--){
        int id=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
        ans += sum(id-1);
        add(id,1);
    }
    cout<<ans; 
}

本题还可以用 归并 或 冒泡 来做，具体内容大家可以看其他题解，我这就不做过多展示了