# UVa 10810

## Summary

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

## Explanation

In a sequence ${\displaystyle A}$, the pair ${\displaystyle (i,j)}$ is an inversion of ${\displaystyle A}$ if ${\displaystyle i and ${\displaystyle A_{i}>A_{j}}$. You have to find the inversions count of given sequences of length ${\displaystyle n<500000}$.

${\displaystyle n}$ is huge; a brute-force ${\displaystyle O(n^{2})}$ bubble sort algorithm won't pass. Similar to UVa 10327, exploit the merge sort algorithm to calculate inversions count.

## Note

In the worst case of a completely unsorted list, (${\displaystyle i,j}$ ${\displaystyle , ${\displaystyle i, ${\displaystyle A_{i}\geq A_{j}}$), number of swaps will equal:

${\displaystyle (n-1)+(n-2)+(n-3)+\ldots +(n-(n-1))={\frac {n(n-1)}{2}}}$

where ${\displaystyle n}$ is the string length. Remembering that we have a huge ${\displaystyle n<5000000}$, maximum number of swaps will equal:

${\displaystyle {\frac {(5000000-1)(5000000-2)}{2}}=12499992500001}$

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.

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

6
0
7