低地距離 (APCS 2020-10 高級)

問題描述

某外星考古隊發現了一處古代遺址中有 \(2n\) 座碉堡排成一列，進一步發現這些碉堡的高度是成對出現，相同高度的碉堡一定恰有兩座。對於每一對相同高度的碉堡，考古隊定義這一對碉堡的「低地距離」為：位於它們之間且高度較低的碉堡數量。考古隊想要計算這一群碉堡的低地距離總和，請你設計一支程式來幫忙計算。

精確地說，若由左至右碉堡高度的序列為 \((h_1,h_2,\ldots,h_{2n})\)，其中 \(1\) 至 \(n\) 的各種高度皆恰好出現兩次。對於 \(1 \le k \le n\)，高度 \(k\) 碉堡的低地距離為

其中 \(h_p=h_q=k\)。

而本題要計算 \(\sum_{k=1}^{n} d(k)\)。

以下是一個 \(n = 4\) 的例子，假設碉堡的高度依序為 \((1,4,3,2,3,1,2,4)\)，我們可以發現高度 \(1\)、\(2\)、\(3\) 與 \(4\) 皆各出現兩次，根據定義，高度 \(1\) 碉堡的低地距離為 \(0\)，因為兩個 \(1\) 之間沒有比 \(1\) 更小的數字；高度 \(2\) 的低地距離為 \(1\)，因為兩個 \(2\) 之間只有一個 \(1\) 是比 \(2\) 小的數字；同樣地，\(3\) 的低地距離也是 \(1\)，而 \(4\) 的低地距離則是 \(5\)。因此，所有高度碉堡的低地距離總和為 \(0 + 1 + 1 + 5 = 7\)。

提示：本題有多種解法，其中一種是將碉堡高度的序列依照高度分成兩個子序列，再以分而治之的策略遞迴求解。另外一種解法是對每一個位置 \(i\)，計算出在 \(i\) 之前而高度小於 \(h_i\) 的碉堡個數。

輸入格式

輸入的第一行是 \(n\)，代表一共有 \(2n\) 座碉堡，\(n\) 不超過 \(10^5\)。第二行有 \(2n\) 個正整數，依序代表由左至右每一座碉堡的高度，高度皆不超過 \(n\)，同一行數字之間以空白間隔。輸入保證相同的高度一定恰好出現兩次，也就是說 \(1\) 至 \(n\) 的每個整數皆出現兩次。

輸出格式

輸出各種高度碉堡的低地距離總和。請注意，答案可能超過 \(2^{31}\)。

範例一：輸入

4
1 4 3 2 3 1 2 4

範例一：正確輸出

7

範例二：輸入

5
1 2 3 4 4 3 2 1 5 5

範例二：正確輸出

0

評分說明

輸入包含若干筆測試資料，對於每一筆測試資料，Python 程式的執行時間限制為 \(3\) 秒，其他程式的執行時間限制為 \(1\) 秒，依正確通過測資筆數給分。其中：

第 \(1\) 子題組 \(20\) 分：\(n\) 不超過 \(1000\)。

第 \(2\) 子題組 \(40\) 分：\(n\) 不超過 \(40000\)。

第 \(3\) 子題組 \(40\) 分：無額外限制。

題目來源

試題來源：程式實作 2020 年 10 月