HDU 1541 Stars：樹狀數組入門經典——統計星星等級

問題描述

給定 N 顆星星的平面坐標 (X, Y)，0 ≤ X, Y ≤ 32000，且無重合點。輸入已按 Y 升序、Y 相同按 X 升序排列。定義一顆星星的「等級」為：不高於且不在其右側的星星數量（即左下方包含自身的點數）。統計每個等級 0 ~ N-1 的星星個數。

核心觀察

因輸入已按 Y 升序給出，處理到第 i 顆星星時，前 i-1 顆星星的 Y 坐標均 ≤ 當前 Y。因此，當前星星的等級 = 已處理星星中 X ≤ 當前 X 的個數。這正是樹狀數組（Fenwick Tree）擅長的動態前綴和問題。

算法流程

1. 初始化樹狀數組 bit[32005]（坐標上限 32000，下標從 1 起，故 X++）。
2. 依次讀入每顆星星 (x, y)，x++ 避免 0 下標。
3. 查詢前綴和 level = query(x)，即當前等級。
4. cnt[level]++ 統計該等級個數。
5. update(x, 1) 將當前星星加入樹狀數組。
6. 最後輸出 cnt[0] ~ cnt[N-1]。

關鍵代碼

int bit[32005], cnt[32005];

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

void update(int i, int v) {
    for (; i <= 32005; i += lowbit(i)) bit[i] += v;
}

int query(int i) {
    int s = 0;
    for (; i > 0; i -= lowbit(i)) s += bit[i];
    return s;
}

int main() {
    int n, x, y;
    while (scanf("%d", &n) != EOF) {
        memset(bit, 0, sizeof(bit));
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; ++i) {
            scanf("%d%d", &x, &y);
            ++x; // 關鍵：x=0 會導致 update 死循環
            int lv = query(x);
            cnt[lv]++;
            update(x, 1);
        }
        for (int i = 0; i < n; ++i)
            printf("%d\n", cnt[i]);
    }
    return 0;
}

複雜度

• 時間：O(N log C)，C = 32000，N ≤ 15000，極快。
• 空間：O(C)。

為什麼要 x++？

樹狀數組下標從 1 開始，lowbit(0) = 0 會導致 update 陷入無限循環。將所有 X 坐標 +1 映射到 [1, 32001] 即可避免此問題。

總結

HDU 1541 是樹狀數組最基礎的應用模型之一：利用輸入順序滿足一維偏序，另一維用樹狀數組維護前綴計數。掌握此題即掌握了「離線偏序 + BIT」的核心範式，為 POJ 2481 Cows、HDU 1348 等進階題打下基礎。