Problem Specification

Given a sequence of n integers, compute the total number of inversions contained within the array. An inversion is formally defined as a pair of indices (i, j) satisfying i < j and A[i] > A[j].

Constraints & Limits

• Sequence length: 1 ≤ n ≤ 10<sup>5</sup>
• Element values: 0 ≤ A[i] ≤ 10<sup>9</sup>
• Time limit: 1000 ms (C/C++) / 2000 ms (Other languages)
• Memory limit: 64 MB (C/C++) / 128 MB (Other languages)

Input Format

The first line contains a single integer n. The second line provides n space-separated integers representing the target sequence.

Output Format

Print a single integer denoting the total inversion count.

Approach 1: Divide and Conquer via Merge Sort

This method adapts the standard merge sort algorithm to accumulate inversion counts during the merge phase. When merging two sorted subarrays, selecting an element from the right partition implies that all remaining elements in the left partition are strictly larger and appear earlier in the original sequence. The count of these unprocessed left elements is added to the global invresion total. This process runs recursively, maintaining O(n log n) time complexity.

#include <iostream>
#include <vector>
using namespace std;

long long inversionTotal = 0;
vector<int> primaryArr, tempBuffer;

void mergeSubarrays(int leftStart, int midPoint, int rightEnd) {
    int leftIdx = leftStart, rightIdx = midPoint + 1;
    int writeIdx = leftStart;

    while (leftIdx <= midPoint && rightIdx <= rightEnd) {
        if (primaryArr[leftIdx] <= primaryArr[rightIdx]) {
            tempBuffer[writeIdx++] = primaryArr[leftIdx++];
        } else {
            inversionTotal += (midPoint - leftIdx + 1);
            tempBuffer[writeIdx++] = primaryArr[rightIdx++];
        }
    }

    while (leftIdx <= midPoint) tempBuffer[writeIdx++] = primaryArr[leftIdx++];
    while (rightIdx <= rightEnd) tempBuffer[writeIdx++] = primaryArr[rightIdx++];

    for (int k = leftStart; k <= rightEnd; ++k) {
        primaryArr[k] = tempBuffer[k];
    }
}

void recursiveSort(int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    recursiveSort(left, mid);
    recursiveSort(mid + 1, right);
    mergeSubarrays(left, mid, right);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    primaryArr.resize(n + 1);
    tempBuffer.resize(n + 1);

    for (int i = 1; i <= n; ++i) {
        cin >> primaryArr[i];
    }

    recursiveSort(1, n);
    cout << inversionTotal << "\n";
    return 0;
}

Approach 2: Fenwick Tree with Coordinate Compression

Direct indexing in a Binary Indexed Tree (BIT) is impractical when element values reach 10<sup>9</sup>. Coordinate compression resolves this by mapping each distinct value to a compact rank in [1, m] while preserving relative ordering. By traversing the original sequence in reverse, we query the BIT for the number of already-processed elements with ranks strictly smaller than the current one. This query result represents valid inversions where the current element serves as the larger value. After recording the count, the current rank is registered in the BIT.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct ElementInfo {
    int value;
    int originalIndex;
};

vector<int> fenwickTree;
int treeCapacity;

inline int extractLowBit(int idx) {
    return idx & -idx;
}

void updateTree(int idx, int delta) {
    for (; idx <= treeCapacity; idx += extractLowBit(idx)) {
        fenwickTree[idx] += delta;
    }
}

long long queryPrefix(int idx) {
    long long accumulation = 0;
    for (; idx > 0; idx -= extractLowBit(idx)) {
        accumulation += fenwickTree[idx];
    }
    return accumulation;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<ElementInfo> dataset(n);
    for (int i = 0; i < n; ++i) {
        cin >> dataset[i].value;
        dataset[i].originalIndex = i + 1;
    }

    sort(dataset.begin(), dataset.end(), [](const ElementInfo& a, const ElementInfo& b) {
        return a.value < b.value;
    });

    vector<int> compressedRanks(n + 1);
    int currentRank = 0;
    int previousVal = -1;

    for (int i = 0; i < n; ++i) {
        if (dataset[i].value != previousVal) {
            currentRank++;
            previousVal = dataset[i].value;
        }
        compressedRanks[dataset[i].originalIndex] = currentRank;
    }

    treeCapacity = n;
    fenwickTree.assign(n + 1, 0);
    long long totalInversions = 0;

    for (int i = n; i >= 1; --i) {
        int rank = compressedRanks[i];
        totalInversions += queryPrefix(rank - 1);
        updateTree(rank, 1);
    }

    cout << totalInversions << "\n";
    return 0;
}