BIT.cpp

/*
    Algorithm : Binary Indexed Tree
    Problem : Counting Inversions in an array of length N
*/

#include <bits/stdc++.h>

using namespace std;

#define MAX 65540
int BIT[MAX];

void update(int pos, int val)
{
    for(; pos<MAX; pos+= pos&(-pos)){
        BIT[pos] += val;
    }
}

int query(int pos)
{
    int sum = 0;
    for(; pos>0; pos-= pos&(-pos)){
        sum += BIT[pos];
    }
    return sum;
}

long long rangeQuery(int l, int r)
{
    long long sum1 = query(r);
    long long sum2 = query(l-1);
    return sum1-sum2;
}

int main()
{
    int n;
    scanf("%d", &n);
    vector<pair<int, int> > V;
    for(int i=0; i<n; i++){
        int val;
        scanf("%d", &val);
        V.push_back(make_pair(val, i));
    }
    sort(V.begin(), V.end());
    int arr[n];
    int sz = 1;
    int idx = V[0].second;
    arr[idx] = sz;
    for(int i=1; i<n; i++){
        if(V[i].first != V[i-1].first){
            sz++;
        }
        int idx = V[i].second;
        arr[idx] = sz;
    }
    memset(BIT, 0, sizeof BIT);
    long long ans = 0;
    for(int i=0; i<n; i++){
        int val = arr[i];
        update(val, 1);
        ans += rangeQuery(val+1, MAX-1);
    }
    printf("%lld\n", ans);
}

/*
    5
    2 3 1 5 4

    3
*/