【牛客算法竞赛入门课第二节例题、习题】逆序数

#include <cstdio>
using namespace std;
const int N = 1e5+10;
const int inf = 1e5;
typedef long long ll;
int tree[N];
int n;
int lowbit(int x){
    return x&(-x);
}
void add(int x,int k){
    while(x <= inf){
        tree[x]+=k;
        x+=lowbit(x);
    }
}
int query(int x){
    int res = 0;
    while(x){
        res+=tree[x];
        x-=lowbit(x);
    }
    return res;
}
int main(){
    int n;scanf("%d",&n);
    ll ans = 0;
    for(int i = 1;i <= n;i++){
        int x;scanf("%d",&x);
        ans+=query(inf) - query(x);
        add(x,1);
    }
    printf("%lld\n",ans);
    return 0;
}