# UVa 10810

From Algorithmist

## 10810 - Ultra-QuickSort[edit]

## Summary[edit]

To find number of adjacent swaps necessary to sort a given sequence of integers.

## Explanation[edit]

In a sequence , the pair is an inversion of if and . You have to find the inversions count of given sequences of length .

is huge; a brute-force bubble sort algorithm won't pass. Similar to UVa 10327, exploit the merge sort algorithm to calculate inversions count.

## Note[edit]

In the worst case of a completely unsorted list, ( , , ), number of swaps will equal:

where is the string length. Remembering that we have a huge , maximum number of swaps will equal:

which far exceeds the capacity of a 32-bit integer. Thus, use 64-bit integers for the inversions count.

Use long long to count swaps.

## Input[edit]

5 9 1 0 5 4 3 1 2 3 5 5 2 3 4 1 0

## Output[edit]

6 0 7