# [APCS] 反序數量

###### tags: `APCS`

## 題目
### 問題敘述
### 輸入格式
### 輸出格式


## 解答
### 題目分析

這個題目要考的主要就是如何依照定義實作出分治法（divide and conquer）的策略。對於學習過演算法的人來說，這題不算難，因為其設計邏輯和所謂的合併排序法（merge sort）幾乎是一樣的。

我們可以用本題的提示中所描述的方法來解說分治法的策略。記得分治法有三個步驟：
1. Divide：將原問題切割成幾個較小的子問題
2. Conquer：分別（遞迴地）解這些較小的子問題
3. Combine：將較小的子問題所得的解答合併，得到原問題的解答

要計算 $A$ 數列的反序量 $W(A)$，可以先將 $A$ 一刀切成左右兩個等長數列 $X$ 與 $Y$（其長度差不超過 1），然後再利用 $W(A) = W(X) + W(Y) + S(X, Y)$ ，其中 $S(X,Y)$ 表示 $X$ 中的數字與 $Y$ 中的數字所構成的反序數量 。分治的好處在於等號右端的 $W(X)$ 與 $W(Y)$ 可以遞迴求解，所以我們只要會設計如何有效的計算 $S(X, Y)$ 就可以輕易地得到一個有效率的程式。也就是說，這題的精髓在於設計一個計算 $S(X, Y)$ 的方法。

### 方法與流程
現在知道這題的設計重點在於如何**有效率**地計算 $S(X,Y)$，我們可以來討論幾種可能的策略。

看似簡單也許不太簡單，如果我們將左邊的每一個跟右邊的每一個做比較，那至少要做 $(n/2)\times (n/2)$ 次比較，這樣的方式複雜度會來到 $O(n^2)$，和暴力法相同，沒有得到分治的好處，因此我們需要一個比 $O(n^2)$ 更好的方法。

假設我們先將 $X$ 與 $Y$ 都各自從小到大排好序，可以怎麼做呢？對排好序的數列，二分搜尋法（binary search）應該有幫助。只要有一邊是排好序的，例如說右邊，我們可以將左邊的每一個元素，對右邊進行二分搜尋法，這樣可以在 $O( n\log(n))$ 的時間完成 $S$ 的計算，整個程式的時間複雜度則是 $O (n\log^2 (n))$，應該對於解題來說是夠好的了。

根據上面的說明，我們可以得到以下遞迴的分治演算法（這邊我們使用左閉右開的區間）：

以解此題來說，以上的說明或許足夠了，但其實我們可以簡單地做到更好。以下說明如何以 $O(n)$ 的時間完成 $S(X,Y)$ 的計算，這可以讓整體時間複雜度降到 $O( n\log (n))$，其實就是使用合併排序法。前面的做法是將一半排序，另外一半對它進行二分搜尋，所以有 $(n/2)$ 個 $\log(n/2)$，加上排序也是 $O( n\log(n))$，所以一層的複雜度是 $O(n\log(n))$。如果兩邊都排好序呢？在兩邊都排好序的情形下，其實是不需要二分搜尋的。

假設我們有兩個**排好序**的陣列 $X$ 與 $Y$，我們要對每一個 $X[i]$ 算出 $Y$ 中有幾個元素小於它。也就是說，對於每個 $X[i]$，我們要找到最小的 $j$，使得 $X[i]\geq Y[j]$，這個 $j$ 就是我們要的數量。

如果 $Y$ 中有 $j$ 個元素小於 $X[i]$，那麼 對於 $X[i+1]$ 以後的元素來說，$Y$ 中小於這個元素的數量一定大於等於 $j$，因為 $X$ 是經過排序的。也就是說， $X[i+1]$ 所要檢查的 $Y$ 的 index 不需要管 $Y[j]$ 的左邊，只要往 $Y[j]$ 的右邊找就行了。根據上面的敘述，我們可以寫出如下的演算法：

這個方法的時間複雜度是多少？雖然是雙層迴圈，但是你可以看到 $i$ 與 $j$ 都是只會往前，永不回頭，每一次比較不管在內層或外層 $i$ 或 $j$ 的值都會增加，所以它的執行時間是與兩陣列總長度的線性關係 $O(n)$。至於排序的部分，又必須花 $O( n\log(n))$，那麼這裡省下來的時間還是沒用！事實上，剛才這個運用兩個指標一路往前爬的方法，就是合併兩個排好序的陣列的過程，也就是 merge。事實上，我們可以一面計算一面合併，計算完成時，兩個陣列也合併成一個排好序的陣列了。根據這個邏輯，可以寫出以下演算法：

為了清楚易懂，上面的說明是以兩個陣列為例，在本題中，是一個陣列的兩個區段，其實沒有不一樣，只是索引值的處理要留意。

### 程式碼
這邊先給出第一種解法的程式碼（使用binary search）：

import bisect  # binary search 的模組

def solution(ary, l, r):
    if r - l < 2:  # base case
        return 0
    m = (l + r) // 2  # 計算中間點

    # 分別對左半邊和右半邊遞迴
    inv = solution(ary, l, m)  # 左半邊
    inv += solution(ary, m, r)  # 右半邊

    tmp = ary[m:r]  # 把右半邊暫存起來
    tmp.sort()  # 將右半邊(R)排序

    for x in ary[l:m]:
        # 對左半邊每個元素在右半邊用binary search尋找
        inv += bisect.bisect_left(tmp, x)
    return inv


if __name__ == "__main__":
    n = int(input())
    ary = [int(x) for x in input().split()]
    print(solution(ary, 0, n))