# APCS實作題2025年11月高級第3題：翻來覆去

> 第1版：2025年11月17日
> 第2版：2025年11月24日，更正標題，這題是 APCS **高級**實作題，不是中高級，我之前弄錯了。
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=r628)

<br />

## 解題想法

直接模擬堆疊操作過程一定會超時，要用二元索引樹 (binary indexed tree, BIT, Fenwick Tree) 計算依序移除每個數字時 pop 的次數。以下的寫法還有改進的空間。
<br /><br />

## Python 程式碼

使用時間約為 1.1 s，記憶體約為 19.4 MB，通過測試。

import sys

class FenwickTree:
    """ binary indexed tree """
    def __init__(self, n):  # 初始化
        self.n = n
        self.tree = [0]*(n+1)  # 必須為 1-indexed

    def _lowbit(self, x):  # 計算最後一個 1
        return x & (-x)

    def update(self, i, delta):  # 單點更新
        while i <= self.n:
            self.tree[i] += delta
            i += self._lowbit(i)

    def query(self, i):  # 查詢 i ~ 1 的總和
        isum = 0
        while i > 0:
            isum += self.tree[i]
            i -= self._lowbit(i)
        return isum

""" 讀取資料 """
n = int(sys.stdin.readline())  # n 個數字
data = list(map(int, sys.stdin.readline().split()))  # 讀取數字
pos = [0]*(n+1)  # 每個數字在的位置，要改成 1-indexed
for i, d in enumerate(data, start=1):
    pos[d] = i
""" 初始化 BIT """
bit = FenwickTree(n)
for i in range(1, n+1):  # 每個點的值都設為 1
    bit.update(i, 1)
""" 計算 pop 的次數 """
pops, curr = 0, 0  # pop 的次數，目前在的位置
for v in range(1, n+1):  # 依序找 1 ~ n
    target = pos[v]  # 目標數字的位置
    if curr == 0:  # 第 1 次操作，區間為 [1, target]
        left, right = 1, target
    else:  # 從第 2 次操作開始，區間為 [min(curr, target), max(curr, target)]
        left = min(curr, target)
        right = max(curr, target)
    pops += bit.query(right) - bit.query(left - 1)  # 更新 pops
    bit.update(target, -1)  # bit 之中 target 位置的值歸零
    curr = target  # 更新 curr 的位置
sys.stdout.write(f"{pops:d}\n")

<br />

## C++ 程式碼

使用時間約為 17 ms，記憶體約為 1.1 MB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long LL;
using namespace std;

class FenwickTree {
private:
    int n;
    vector<int> tree;
    inline int lowbit(int x) {
        return x & (-x);
    }

public:
    // 建構子，節點數量為 size
    FenwickTree(int size) : n(size), tree(size+1, 0) {}
    
    // 單點更新
    void update(int i, int delta) {
        while(i <= n) {
            tree[i] += delta;
            i += lowbit(i);
        }
    }

    // 查詢索引值 i ~ 1 的總和
    int query(int i) {
        int isum = 0;
        while(i > 0) {
            isum += tree[i];
            i -= lowbit(i);
        }
        return isum;
    }

    // 查詢索引值 [left, right] 的總和
    int range_query(int left, int right) {
        if (left >= right) return 0;
        return query(right) - query(left - 1);
    }
};

int main() {
    int n; scanf("%d", &n);
    vector<int> pos (n+1);
    for(int i=1; i<=n; i++) {
        int v; scanf("%d", &v);
        pos[v] = i;
    }
    FenwickTree bit(n);
    for(int i=1; i<=n; i++) {
        bit.update(i, 1);
    }
    LL pops = 0;
    int curr = 0;
    for(int v=1; v<=n; v++) {
        int left, right, target = pos[v];
        if (curr == 0) {
            left = 1;
            right = target;
        } else {
            left = min(curr, target);
            right = max(curr, target);
        }
        pops += bit.range_query(left, right);
        bit.update(target, -1);
        curr = target;
    }
    printf("%lld\n", pops);
    return 0;
}

<br /><br />

---

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