ZeroJudge 解題筆記：d788. 排名順序

作者：王一哲
日期：2026年5月25日


ZeroJudge 題目連結：d788. 排名順序

解題想法

這題理論上可以用線段樹解題，但是 Python 的速度太慢，即使程式碼邏輯正確仍會超時，改用二元索引樹才過關。用分數當作 tree 的索引值，tree[i] 的值代表這個分數的人數。假設每次加入討論的人分數為 x，先執行 bit.update(x)，再計算 bit.query(x-1)，也就是分數比自己低的人數，則自己的名次 = 總人數 - bit.query(x-1)。

Python 程式碼

線段樹，超時。

# --- 自訂線段樹類別，單點修改 ---
class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.data = [0]*self.n  
        self.tree = [0]*(4*self.n)  # 長度開 4 倍確保不會出界
        # 由於本題一開始 self.data, self.tree 皆為 0，省略 _build

    def _update(self, node, start, end, target, val):
        if start == end:
            self.tree[node] = val
            self.data[target] = val
            return
        mid = (end - start) // 2 + start
        if target <= mid:
            self._update(2*node + 1, start, mid, target, val)
        else:
            self._update(2*node + 2, mid + 1, end, target, val)
        self.tree[node] = self.tree[2*node + 1] + self.tree[2*node + 2]

    def _query(self, node, start, end, left, right):
        if end < left or start > right:
            return 0
        if left <= start and right >= end:
            return self.tree[node]
        mid = (end - start) // 2 + start
        lsum = self._query(2*node + 1, start, mid, left, right)
        rsum = self._query(2*node + 2, mid + 1, end, left, right)
        return lsum + rsum

    # --- 外部呼叫函式 ---
    def update(self, target, val):
        self._update(0, 0, self.n - 1, target, val)

    def query(self, left, right):
        return self._query(0, 0, self.n - 1, left, right)

def solve():
    import sys
    
    maxn = 100001
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        st = SegmentTree(maxn)  # 分數 0 ~ 100000 是否有人
        for i in range(1, n+1):
            m = int(data[ptr])
            ptr += 1
            st.update(m, 1)
            # 分數 m 的名次 = 總人數 - 分數 0 到 m-1 的人數
            result.append(f"{i - st.query(0, m-1):d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

二元索引樹，使用時間約為 5.1 s，記憶體約為 162.7 MB，通過測試。

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)

    def _lowbit(self, x):
        return x & (-x)
    
    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += self._lowbit(i)

    def query(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= self._lowbit(i)
        return total

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        N = int(data[ptr])
        ptr += 1
        bit = FenwickTree(N)
        for i in range(1, N+1):
            M = int(data[ptr])
            ptr += 1
            bit.update(M, 1)  # 分數 M 的人數加 1
            result.append(f"{i - bit.query(M-1):d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

線段樹，使用時間約為 0.4 s，記憶體約為 4.9 MB，通過測試。

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

class SegmentTree {
private:
    int n;
    vector<int> data, tree;

    /* 內部遞迴函式，省略 _build */
    void _update(int node, int start, int end, int target, int val) {
        if (start == end) {
            tree[node] = val;
            data[target] = val;
            return;
        }
        int mid = (end - start) / 2 + start;
        if (target <= mid) {
            _update(2*node + 1, start, mid, target, val);
        } else {
            _update(2*node + 2, mid + 1, end, target, val);
        }
        tree[node] = tree[2*node + 1] + tree[2*node + 2];
    }

    int _query(int node, int start, int end, int left, int right) {
        if (end < left || start > right) {
            return 0;
        }
        if (left <= start && right >= end) {
            return tree[node];
        }
        int mid = (end - start) / 2 + start;
        int lsum = _query(2*node + 1, start, mid, left, right);
        int rsum = _query(2*node + 2, mid + 1, end, left, right);
        return lsum + rsum;
    }

public:
    // 建構子，省略呼叫 _build
    SegmentTree(int maxn) {
        n = maxn;
        data.assign(maxn, 0);
        tree.assign(4*maxn, 0);
    }
    /* 外部呼叫函式 */
    void update(int target, int val) {
        _update(0, 0, n-1, target, val);
    }

    int query(int left, int right) {
        return _query(0, 0, n-1, left, right);
    }
};

int main() {
    const int maxn = 100001;
    int n;
    while(scanf("%d", &n) != EOF) {
        SegmentTree st(maxn);
        for(int i=1; i<=n; i++) {
            int m;
            scanf("%d", &m);
            st.update(m, 1);
            printf("%d\n", i - st.query(0, m-1));
        }
    }
    return 0;
}

二元索引樹，使用時間約為 0.2 s，記憶體約為 3.3 MB，通過測試。

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

class FenwickTree {
private:
    int n;
    vector<int> tree;

public:
    FenwickTree(int size) {
        n = size;
        tree.assign(n+1, 0);
    }

    int _lowbit(int x) {
        return x & (-x);
    }

    void update(int i, int delta) {
        while(i <= n) {
            tree[i] += delta;
            i += _lowbit(i);
        }
    }

    int query(int i) {
        int total = 0;
        while(i > 0) {
            total += tree[i];
            i -= _lowbit(i);
        }
        return total;
    }
};

int main() {
    int N;
    while(scanf("%d", &N) != EOF) {
        FenwickTree bit(N);
        for(int i=1; i<=N; i++) {
            int M;
            scanf("%d", &M);
            bit.update(M, 1);
            printf("%d\n", i - bit.query(M-1));
        }
    }
    return 0;
}