Inversion Count by BIT

#include<bits/stdc++.h>

#define N 10000009

#define ll long long int

using namespace std;

ll tree[N], a[N];

ll query(int indx)

{

    ll sum = 0;

    while(indx > 0)

    {

        sum += tree[indx];

        indx -= (indx & (-indx));

    }

    return sum;

}

void update(int indx, int value, int n)

{

    while(indx <= n)

    {

        tree[indx] += value;

        indx += (indx & (-indx));

    }

}

ll invcnt(int n, ll mx)

{

    ll cnt = 0;

    for(int i=n-1; i>=0; i--)

    {

        cnt += query(a[i]-1);

        update(a[i], 1, mx);

    }

    return cnt;

}

int main()

{

    int n;

    cin >> n;

    ll mx = 0;

    for(int i=0; i<n; i++)

    {

        cin >> a[i];

        mx = max(a[i], mx);

    }

    cout << invcnt(n, mx) << "\n";

    return 0;

}