# APCS實作題2020年10月第4題：低地距離

> 日期：2024年9月8日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f315)

## 題目

### 問題描述

輸入一個長度為 $2n$ 的陣列，其中 $1$ ~ $n$ 的每個數字都剛好各 $2$ 次。
$i$ 的低窪值的定義是兩個數值為 $i$ 的位置中間，有幾個小於 $i$ 的的數字。
以 $[3, 1, 2, 1, 3, 2]$ 為例，$1$ 的低窪值為 $0$，$2$ 的低窪值值為 $1$，$3$ 的低窪值為 $3$。
請對於每個 $1$ ~ $n$ 的數字都求其低窪值（兩個相同的數字之間有幾個數字比它小），輸出低窪值的總和，答案可能會超過 C++ int 的上限。<br />

### 輸入說明

第一行有一個正整數 $n$
第二行有 $2n$ 個正整數，以空格分隔，保證 $1$ ~ $n$ 每個數字都恰好出現兩次。

配分
- 20%：$1 \leq n \leq 1000$
- 40%：$1 \leq n \leq 40000$
- 40%：$1 \leq n \leq 100000$
<br />

### 輸出說明

輸出 $1$ ~ $n$ 每個數字的低窪值總和。
<br />

### 範例輸入

3
3 1 2 1 3 2

### 範例輸出

4

<br />

## Python 程式碼

### 寫法1，使用 set 及遞迴

費時最久約為 1.8 s，使用記憶體最多約為 38.3 MB，通過測試。

""" 分治法，輸入串列 arr，下限 low，上限 high """
def sol(arr, low, high):
    if len(arr) <= 2: return 0  # 遞迴出口，長度小於等於2，不能再切
    mid = (high - low) // 2 + low  # 取中間值
    d = 0  # 答案
    small = []  # 小於等於 mid 的資料
    large = []  # 大於等於 mid 的資料
    # 找某個數字位於多少大數對之間，大數 x 第一次出現時加入 between；x 第二次出現時已離開大數對範圍，從 between 移除。
    between = set()
    for e in arr:  # 由 arr 依序取出資料 e
        if e <= mid:  # e 小於等於 mid
            d += len(between)  # 更新 d，加上 between 的長度
            small.append(e)  # e 加入 small
        else:
            large.append(e)  # e 加入 large
            if e in between: between.remove(e)  # 如果 e 在 between 之中則移除
            else: between.add(e)  # 否則將 e 加入 between
    # 結束 for 迴圈
    d += sol(small, low, mid)  # 遞迴，找小於等於 x 的部分
    d += sol(large, mid+1, high)  # 遞迴，找大於等於 x 的部分
    return d  # 回傳 d
""" 結束自訂函式 """

n = int(input())
a = list(map(int, input().split()))
d = sol(a, 1, n)
print(d)

<br /><br />

### 寫法2，找同一個數字之前小於此數的數字數量再相減

為了判斷某個數字 x 是第一次或第二次出現，需要修改原來的資料，例如將第一個 x 改為 2x，第二個 x 改為 2x-1，則數字範圍由 1 到 n 變為 1 到 2n。費時最久約為 2.5 s，使用記憶體最多約為 31.9 MB，通過測試。

""" 計算同一個數字出現的位置之有幾個較小的數字再相減 """
def sol(arr):
    global total
    if len(arr) < 2: return 0  # 遞迴出口，長度小於等於2，不能再切
    mid = len(arr) // 2  # 串列長度的一半
    left = arr[:mid]  # 左半部
    right = arr[mid:]  # 右半部
    sol(left)  # 遞迴，解左半部
    sol(right)  # 遞迴，解右半部
    # 合併左半部及右半部
    i, li = 0, 0  # arr 的索引值 i，left 的索引值 li
    for x in right:  # 從右半部依序取出數字 x
        while li < len(left) and left[li] <= x:  # 如果 li 還沒有出界，而且 left[li] 小於等於 x
            arr[i] = left[li]  
            i += 1; li += 1
        if x&1: total += li  # 如果 x 第二次出現，total 加上 li
        else: total -= li  # 如果 x 第二次出現，total 減去 li
        arr[i] = x
        i += 1
    arr[i:] = left[li:]
""" 結束自訂函式 """

n = int(input())  # 讀取數子上限 n
a = list(map(int, input().split()))  # 讀取資料 a
t = [0]*(n+1)  # 1 ~ n 各數字出現次數
for i in range(len(a)):  # 依序産生 0 ~ n-1
    y = a[i]  # 正在處理的數值 y
    a[i] = y*2 - t[y]  # 將 a[i] 修改成 2*y（第一次出現）或 2*y - 1（第二次出現）
    t[y] = 1  # y 出現次數加 1
total = 0  # 答案，預設為 0
sol(a)  # 呼叫 sol，代入 a 求答案
print(total)  # 印出答案

<br /><br />

### 寫法3，使用二元索引樹 (binary index tree, BIT)

<img height="100%" width="100%" src="https://upload.wikimedia.org/wikipedia/commons/7/70/16-node_Fenwick_tree.svg" style="display: block; margin-left: auto; margin-right: auto;"/>
<div style="text-align:center">BIT 結構示意圖</div>
<br /><br />

費時最久約為 2 s，使用記憶體最多約為 41.8 MB，通過測試。

def update(bit, idx, val):  # 從 idx 開始向下更新節點
    i = idx  # 索引值 i
    while i <= len(bit):  # 如果 i 還沒有出界繼續執行
        bit[i] += val  # 更新 bit[i]，加上 val
        i += i&(-i)  # 移到子節點

def psum(bit, n):  # 計算前 n 項的和
    result = 0  # 加總
    i = n  # 索引值預設為 i
    while i:  # 當 i > 0 時繼續執行
        result += bit[i]  # result 加上 bit[i]
        i -= i&(-i)  # 移到父節點
    return result  # 回傳加總

n = int(input())  # 讀取高度最大值 n
line = list(map(int, input().split()))  # 讀取每個位置的高度
arr = [[0, 0] for _ in range(n+1)]  # 數字 1 ~ n 兩次出現的位置，開頭多了一組 [0, 0]
for i, x in enumerate(line, start=1):  # 依序由 line 取出位置 i、數字 x
    if arr[x][0] == 0: arr[x][0] = i  # 如果是第1個 x，更新 arr[x][0]
    else: arr[x][1] = i  # 如果是第2個 x，更新 arr[x][1] 

bit = [0]*(2*n+1)  # binary index tree，共有 2*n+1 個節點，節點 0 沒有資料
ans = 0  # 答案
for i in range(1, n+1):  # 依照 i = 1 ~ n 出現的位置，修改 bit 中相關結點儲存的數量
    ans += psum(bit, arr[i][1]-1) - psum(bit, arr[i][0])  # ans 加上 psum[right-1] ~ psum[start]
    update(bit, arr[i][0], 1)  # 呼叫 update，更新 bit 中的 arr[i][0]，數量加 1
    update(bit, arr[i][1], 1)  # 呼叫 update，更新 bit 中的 arr[i][1]，數量加 1

print(ans)  # 印出答案

<br /><br />

### 寫法4，使用線段樹

第3筆測資就超時，但是程式碼邏輯是對的，改寫成 C++ 版本就能通過測試。

""" 自訂函式，更新線段樹，輸入儲存樹用的串列 tree，根節點編號 node，
    節點編號 start ~ end，要修改的索引值 idx，要加上或減去的差值 val """
def update(tree, node, start, end, idx, val):
    if start == end:  # 遞迴出口
        tree[node] += val  # tree[node] 的加上 val
        return
    mid = (end - start) // 2 + start  # 中間值
    leftNode = 2*node + 1  # 左子樹節點編號
    rightNode = 2*node + 2  # 右子樹節點編號
    if idx >= start and idx <= mid:  # idx 在左子樹
        update(tree, leftNode, start, mid, idx, val)
    else:  # idx 在右子樹
        update(tree, rightNode, mid+1, end, idx, val)
    tree[node] = tree[leftNode] + tree[rightNode]  # node 的值為左、右子樹節點相加

""" 自訂函式，找 [L, R] 區間加總 """
def query(tree, node, start, end, L, R):  # 計算前 [L, R] 區間和
    if R < start or L > end: return 0  # 遞迴出口，[L, R] 和 [start, end] 沒有重疊
    # 遞迴出口，要找的範圍只剩一個點或者 [start, end] 在 [L, R] 之間
    if start == end or (L <= start and R >= end): return tree[node]
    mid = (end - start) // 2 + start  # 中間值
    leftNode = 2*node + 1  # 左子樹節點編號
    rightNode = 2*node + 2  # 右子樹節點編號
    sumLeft = query(tree, leftNode, start, mid, L, R)  # 遞迴，找左子樹
    sumRight = query(tree, rightNode, mid+1, end, L, R)  # 遞迴，找右子樹
    return sumLeft + sumRight  # 回傳左、右子樹加總
    
""" 解題過程 """
n = int(input())  # 讀取高度最大值 n
line = list(map(int, input().split()))  # 讀取每個位置的高度
arr = [0]*(2*n)  # 數字 1 ~ n 兩次出現的位置，2個一組
cnt = [0]*(n+1)  # 數字 1 ~ n 兩次出現的次數，開頭多1個0
for i, x in enumerate(line):  # 依序由 line 取出位置 i、數字 x
    if cnt[x] == 0:  # 如果 x 還沒有出現過
        cnt[x] += 1  # cnt[x] 加 1
        arr[2*x-2] = i  # 如果是第1個 x，更新 arr[2*x-2]
    else: arr[2*x-1] = i  # 如果是第2個 x，更新 arr[2*x-1]

tree = [0]*(4*2*n)  # 線段樹，陣列長度是資料點數量 2*n 的4倍
ans = 0  # 答案
for i in range(1, n+1):  # 依照 i = 1 ~ n 出現的位置，修改 tree 中相關結點儲存的數量
    ans += query(tree, 0, 0, 2*n-1, arr[2*i-2]+1, arr[2*i-1]-1)  # ans 加上 i 兩個位置之間已填入的資料數量
    update(tree, 0, 0, 2*n-1, arr[2*i-2], 1)  # 呼叫 update，更新 tree 中的 arr[2*i-2]，數量加 1
    update(tree, 0, 0, 2*n-1, arr[2*i-1], 1)  # 呼叫 update，更新 tree 中的 arr[2*i-1]，數量加 1
print(ans)  # 印出答案

<br /><br />

## C++ 程式碼

### 寫法1，使用 set 及遞迴

用 int 會溢位，要使用 long。費時最久約為 0.4 s，使用記憶體最多約為 8.5 MB，通過測試。

#include <iostream>
#include <vector>
#include <set>
using namespace std;

/* 分治法，輸入串列 arr，下限 low，上限 high */
long sol(vector<long>& arr, long low, long high) {
    if (arr.size() <= 2) return 0;  // 遞迴出口，長度小於等於2，不能再切
    long d = 0, mid = (high - low) / 2 + low;  // 答案 d，中間值 mid
    vector<long> large, small;  // 大於等於 mid 的資料，小於等於 mid 的資料
    set<long> between;  // 找某個數字位於多少大數對之間
    for(long e : arr) {  // 由 arr 依序取出資料 e
        if (e <= mid) {  // e 小於等於 mid
            d += between.size();  // 更新 d，加上 between 的長度
            small.push_back(e);  // e 加入 small
        } else {
            large.push_back(e);  // e 加入 large
            if (between.count(e) == 1) between.erase(e);  // 如果 e 在 between 之中則移除
            else between.insert(e);  // 否則將 e 加入 between
        }
    }
    d += sol(small, low, mid);  // 遞迴，找小於等於 x 的部分
    d += sol(large, mid+1, high);  // 遞迴，找大於等於 x 的部分
    return d;  // 回傳 d
}

int main() {
    long n; cin >> n;
    vector<long> a (2*n, 0);
    for(long i=0; i<2*n; i++) cin >> a[i];
    cout << sol(a, 1, n) << "\n";
    return 0;
}

<br /><br />

### 寫法2，使用二元索引樹 (binary index tree, BIT)

用 int 會溢位，要使用 long。費時最久約為 37 ms，使用記憶體最多約為 2.6 MB，通過測試。

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

void update(vector<long>& bit, int idx, int val) {
    for(int i=idx; i<=(int)bit.size(); i+=i&(-i))
        bit[i] += (long)val;
}

long psum(vector<long>& bit, int n) {
    long result = 0;
    for(int i=n; i>0; i-=i&(-i))
        result += bit[i];
    return result;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<pair<int, int>> arr (n+1, make_pair(0, 0));
    for(int i=1; i<=2*n; i++) {
        int x; cin >> x;
        if (arr[x].first == 0) arr[x].first = i;
        else arr[x].second = i;
    }
    vector<long> bit (2*n+1, 0);
    long ans = 0;
    for(int i=1; i<=n; i++) {
        ans += psum(bit, arr[i].second - 1) - psum(bit, arr[i].first);
        update(bit, arr[i].first, 1);
        update(bit, arr[i].second, 1);
    }
    cout << ans << "\n";
    return 0;
}

<br /><br />

### 寫法3，使用線段樹

用 int 會溢位，要使用 long。費時最久約為 0.1 s，使用記憶體最多約為 7.6 MB，通過測試。

#include <iostream>
#include <vector>
using namespace std;

/* 自訂函式，更新線段樹，輸入儲存樹用的串列 tree，根節點編號 node，
    節點編號 start ~ end，要修改的索引值 idx，要加上或減去的差值 val */
void update(vector<long>& tree, int node, int start, int end, int idx, long val) {
    if (start == end) {  // 遞迴出口
        tree[node] += val;  // tree[node] 的加上 val
        return;
    }
    int mid = (end - start) / 2 + start;  // 中間值
    int leftNode = 2*node + 1;  // 左子樹節點編號
    int rightNode = 2*node + 2;  // 右子樹節點編號
    if (idx >= start && idx <= mid)  // idx 在左子樹
        update(tree, leftNode, start, mid, idx, val);
    else  // idx 在右子樹
        update(tree, rightNode, mid+1, end, idx, val);
    tree[node] = tree[leftNode] + tree[rightNode];  // node 的值為左、右子樹節點相加
}

/* 自訂函式，找 [L, R] 區間加總 */
long query(vector<long>& tree, int node, int start, int end, int L, int R) {
    if (R < start || L > end) return 0;  // 遞迴出口，[L, R] 和 [start, end] 沒有重疊
    // 遞迴出口，要找的範圍只剩一個點或者 [start, end] 在 [L, R] 之間
    if (start == end || (L <= start and R >= end)) return tree[node];
    int mid = (end - start) / 2 + start;  // 中間值
    int leftNode = 2*node + 1;  // 左子樹節點編號
    int rightNode = 2*node + 2;  // 右子樹節點編號
    long sumLeft = query(tree, leftNode, start, mid, L, R);  // 遞迴，找左子樹
    long sumRight = query(tree, rightNode, mid+1, end, L, R);  // 遞迴，找右子樹
    return sumLeft + sumRight;  // 回傳左、右子樹加總
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;  // 讀取高度最大值 n
    vector<int> arr (2*n, 0);  // 數字 1 ~ n 兩次出現的位置，2個一組
    vector<int> cnt (n+1, 0);  // 數字 1 ~ n 兩次出現的次數，開頭多1個0
    for(int i=0; i<2*n; i++) {  // 讀取 2*n 個高度
        int x; cin >> x;
        if (cnt[x] == 0) {  // 如果 x 還沒有出現過
            cnt[x]++;  // cnt[x] 加 1
            arr[2*x-2] = i;  // 如果是第1個 x，更新 arr[2*x-2]
        } else arr[2*x-1] = i;  // 如果是第2個 x，更新 arr[2*x-1]
    }
    vector<long> tree (4*2*n, 0);  // 線段樹，陣列長度是資料點數量 2*n 的4倍
    long ans = 0;  // 答案
    for(int i=1; i<=n; i++) {  // 依照 i = 1 ~ n 出現的位置，修改 tree 中相關結點儲存的數量
        ans += query(tree, 0, 0, 2*n-1, arr[2*i-2]+1, arr[2*i-1]-1);  // ans 加上 i 兩個位置之間已填入的資料數量
        update(tree, 0, 0, 2*n-1, arr[2*i-2], 1);  // 呼叫 update，更新 tree 中的 arr[2*i-2]，數量加 1
        update(tree, 0, 0, 2*n-1, arr[2*i-1], 1);  // 呼叫 update，更新 tree 中的 arr[2*i-1]，數量加 1
    }
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

## 參考資料

1. 吳邦一教授的 APCS 解題影片〈[PyAp45 Python APCS 題解：低地距離(AP202010_4), ZeroJudge f315](https://youtu.be/IkZADcf3lcE?si=UMibzXb50j6xbt2r)〉
2. [【資料結構】二元索引樹 | 樹狀數組 | Fenwick Tree | Binary Indexed Tree](https://youtu.be/ErmFGGw7f-s?si=iu-HsqIJgKInuH8K)
3. [樹狀數組](https://youtu.be/v2Q4ZjPeFuc?si=RWpbwjH6l4b4-_Fq)
4. [线段树 (segment tree)](https://youtu.be/e_bK-dgPvfM?si=xO1anO0X13PdFd7k)

---

###### tags:`APCS`、`Python`、`C++`