HKOJ 1109 - A sort of Shell

題目大意︰大約是每一個command以最少的swapping做partial的bubble sort，問最後做完所有command之後做了多少次swapping。

由於array的長度達100,000，因此simulation是不夠快的  Complexity: O(N²)

Observation 1:
其實已在題目大意標明，這是一個partial的bubble sort。

Observation 2:
每一個bubble sort的minimum number of swapping是number of inversion，因此我們只需快速地計inversion的數目，便可以快速地simulate整個程序。

Inversion即是

For each i and j, where i<j
If Ai>Aj, then this counts as one inversion

因此，我們可以逐個command去simulate，每一個command，我們可以用merge sort去數，這只需要O(N log N)的時間。具體方法請自己想想，或是上網search。

總時間是O(MN log N)。

注意︰之前test data是錯誤的，我測試sample solution之後肯定了該錯誤，現在test data已經更正。建議WA的同學可試試這個case:

5 3
9 9 9 9 9
4 2 1

正確答案是0，而sample solution出的是14。