逆序数

树状数组简单应用，逆序数转换为：求前i个数小于x的和。

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;

typedef long long ll;
const int maxn=2e5+10;
int sum[maxn],cnt=maxn-1;

void add( int x ) { while( x<=cnt ) sum[x]++,x+=lowbit(x); }
int query( int x ,int ans=0 ) { while( x ) ans+=sum[x],x-=lowbit(x);return ans; }  

int main()
{
    int n;
    cin>>n;
    ll ans=0;
    for( int i=1;i<=n;i++ ) 
    {
        int x;cin>>x;x=1e5+10-x;
        ans+=query(x-1);
        add(x);
    }
    cout<<ans<<endl;
}