Count the Inversions — Solution & Editorial

Back to the Problem

Merge sort while counting: when an element of the right half is placed before remaining left-half elements, it forms that many inversions. A BIT over compressed values works equally well.

Complexity: O(N log N)

Watch out: Up to ~5×10⁹ inversions — the counter must be 64-bit.