Как посчитать число инверсий в массиве через дерево Фенвика за O(n log n)?

Идея: идём по массиву слева направо, для каждого a[j] считаем, сколько уже встреченных элементов больше него — это вклад в инверсии. Поддерживаем BIT частот по значениям: уже добавленных элементов всего j, из них ≤ a[j] штук — это query(a[j]), значит больших — j - query(a[j]).

Значения большие → сжимаем координаты (ранги от 1).

long long countInversions(vector<int> a){
    int n = a.size();
    vector<int> srt(a);
    sort(srt.begin(), srt.end());
    srt.erase(unique(srt.begin(), srt.end()), srt.end());
    auto rank = [&](int x){
        return int(lower_bound(srt.begin(), srt.end(), x) - srt.begin()) + 1;
    };
    BIT bit((int)srt.size());
    long long inv = 0;
    for (int j = 0; j < n; ++j) {
        int r = rank(a[j]);
        inv += j - bit.query(r); // среди j добавленных — сколько > a[j]
        bit.update(r, 1);
    }
    return inv;
}

Сложность: сжатие O(n log n), основной цикл n запросов/обновлений по O(log n) — итого O(n log n) время, O(n) память. Результат до n²/2 ≈ 5·10^11 для n=10^6 — обязательно long long.