逆序数

树状数组模板题、归并也行

树状数组，先查询树状数组内当前有多少个数比当前的数字大，然后再把数字更新上去即可。。

#include<bits/stdc++.h>
using namespace std;
int c[1<<17];
int n;
void add(int x){
    for(;x<=n;x+=x&-x) c[x]++;
}
int get(int x){
    int ans=0;
    for(;x;x-=x&-x) ans+=c[x];
    return ans;
}
int main(){
    cin>>n;
    long long ans=0;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        ans += get(n)-get(x);
        add(x);
    }
    cout<<ans;
    return 0;
}