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

題目大意

給定 n (≤ 15000) 顆星星的坐標 (x, y)，已按 y 升序、y 相同按 x 升序輸入。
星星等級 = 左下方（含同列同行）星星數量。輸出每個等級的星星個數。

核心觀察：一維化 + 前綴和

因輸入已按 y 排序，處理到第 i 顆星星時，所有 y' ≤ y_i 的星星已處理完畢。
只需統計已處理星星中 x' ≤ x_i 的個數 → 樹狀數組維护 x 軸前綴和。

算法流程

1. x 坐標範圍 [0, 32000]，樹狀數組大小 32002（1-based 索引，x+1）。
2. 遍歷星星：

int level = bit.query(x + 1);  // 查詢 ≤ x 的星星數
ans[level]++;
bit.add(x + 1, 1);  // 插入當前星星

3. 最後輸出 ans[0] ... ans[n-1]。

C++ 參考代碼

const int MAXX = 32002;
int bit[MAXX], ans[15005];

int lowbit(int x) { return x & -x; }
void add(int x, int v) { for (; x < MAXX; x += lowbit(x)) bit[x] += v; }
int query(int x) { int r = 0; for (; x; x -= lowbit(x)) r += bit[x]; return r; }

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        memset(bit, 0, sizeof(bit));
        memset(ans, 0, sizeof(ans));
        for (int i = 0, x, y; i < n; ++i) {
            scanf("%d%d", &x, &y);
            int lvl = query(x + 1);
            ans[lvl]++;
            add(x + 1, 1);
        }
        for (int i = 0; i < n; ++i) printf("%d\n", ans[i]);
    }
    return 0;
}

複雜度分析

• 時間：O(n log MAXX) ≈ 15000 * 15，極快。
• 空間：O(MAXX) ≈ 128 KB。

避坑指南

1. x 可能為 0，樹狀數組下標從 1 開始，故用 x+1。
2. 輸入可能多組測試數據，循環讀取直到 EOF。
3. 輸出共 n 行，即使某等級為 0 也要輸出 0。

舉一反三

• 逆序對計數：相同模板，從右向左遍歷查詢 query(x-1)。
• 二維偏序問題：CDQ 分治 / 離線 + BIT 通用框架。
• 動態區間第 k 小：樹狀數組上二分 / 主席樹。