ZeroJudge 解題筆記：d794. 世界排名

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


ZeroJudge 題目連結：d794. 世界排名

解題想法

d788. 排名順序 的加強版，分數 $M$ 改成 $1 \leq M \leq 2^{64} - 1$。 由於分數差異極大，而且不是每個分數都有人，還要再加上離散化，用分數由小到大的順序當成新的編號，用編號存入線段樹或二元索引樹之中解題。這題理論上可以用線段樹解題，但是 Python 的速度太慢，即使程式碼邏輯正確仍會超時，改用二元索引樹才過關。

Python 程式碼

使用時間約為 12.9 s，記憶體約為 328.6 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
        scores = list(map(int, data[ptr:ptr+N]))  # 讀取 N 個成績
        ptr += N
        sorted_unique = sorted(set(scores))  # 去重並排序
        rank_map = {val: rank for rank, val in enumerate(sorted_unique, start=1)}
        bit = FenwickTree(N)
        for i in range(1, N+1):
            rank = rank_map[scores[i-1]]  # 分數轉成順序
            bit.update(rank, 1)  # rank 的人數加 1
            result.append(f"{i - bit.query(rank-1):d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

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

#include <cstdio>
#include <vector>
#include <algorithm>
typedef unsigned long long LL;
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) {
        if (left > right) return 0;  // 防呆
        return _query(0, 0, n-1, left, right);
    }
};

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        vector<LL> m_vals, scores;
        for(int i=0; i<n; i++) {
            LL score;
            scanf("%lld", &score);
            m_vals.push_back(score);
            scores.push_back(score);
        }
        // 離散化 + 去重
        sort(scores.begin(), scores.end());  // 排序
        scores.erase(unique(scores.begin(), scores.end()), scores.end());
        // 用去重後的數量建立線段樹
        SegmentTree st((int)scores.size());
        // 處理查詢
        for(int i=0; i<n; i++) {
            int rank = lower_bound(scores.begin(), scores.end(), m_vals[i]) - scores.begin();
            st.update(rank, 1);
            int less_cnt = 0;
            if (rank > 0) {
                less_cnt = st.query(0, rank - 1);
            }
            printf("%d\n", i + 1 - less_cnt);
        }
    }
    return 0;
}

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

#include <cstdio>
#include <vector>
#include <unordered_map>
#include <algorithm>
typedef unsigned long long LL;
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) {
        vector<LL> scores (N);
        for(int i=0; i<N; i++) {
            scanf("%llu", &scores[i]);
        }
        vector<LL> sorted_unique (scores.begin(), scores.end());
        sort(sorted_unique.begin(), sorted_unique.end());
        sorted_unique.erase(unique(sorted_unique.begin(), sorted_unique.end()), sorted_unique.end());
        unordered_map<LL, int> rank_map;
        for(int i=0; i<N; i++) {
            rank_map[sorted_unique[i]] = i+1;
        }
        FenwickTree bit(N);
        for(int i=1; i<=N; i++) {
            int rank = rank_map[scores[i-1]];
            bit.update(rank, 1);
            printf("%d\n", i - bit.query(rank-1));
        }
    }
    return 0;
}