HDU 1541 Stars —— 樹狀數組入門：二維偏序統計星星等級

HDU 1541：給 N ≤ 15000 顆星星，座標 (X, Y)，0 ≤ X, Y ≤ 32000。輸入已按 Y 升序、同 Y 按 X 升序。星星等級 = 左下區域（x' ≤ x 且 y' ≤ y）其他星星數。求每個等級 0~N-1 的星星個數。經典一維樹狀數組離線處理二維偏序模板題。

一、問題轉化

因輸入已按 Y 排序，掃描時當前星星的 Y 均 ≥ 已處理星星。只需統計已處理星星中 X ≤ 當前X 的個數 → 一維前綴和 → 樹狀數組維護 X 軸頻率。

二、樹狀數組核心

const int MAXX = 32001; // X 範圍 0~32000，內部下標 1-based
int bit[MAXX];

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

void add(int x, int v) { // x 為 1-based
    for (; x < MAXX; x += lowbit(x)) bit[x] += v;
}

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

三、主流程

int level[15000], ans[15000];
for (int i = 0; i < N; ++i) {
    int x, y; scanf("%d%d", &x, &y);
    int lv = sum(x + 1); // X 從 0 開始，樹狀數組 1-based
    level[i] = lv;
    ++ans[lv];
    add(x + 1, 1);
}
for (int i = 0; i < N; ++i) printf("%d\n", ans[i]);

四、完整 AC 代碼

#include <cstdio>
#include <cstring>
const int MAXN = 15005;
const int MAXX = 32005;
int bit[MAXX], ans[MAXN];

int lowbit(int x) { return x & -x; }
void add(int x) { for (; x < MAXX; x += lowbit(x)) ++bit[x]; }
int sum(int x) { int s=0; for(; x>0; x-=lowbit(x)) s+=bit[x]; return s; }

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

五、複雜度

• 時間：O(N log Xmax) ≈ 15000 × 15 = 2.25×10⁵ 操作，極快。
• 空間：O(Xmax) = 32005 int。

六、關鍵點

1. 輸入已按 Y 排序，將二維偏序降維為一維前綴和。
2. X 範圍 0~32000，樹狀數組下標 +1 避開 0。
3. 等級最大 N-1，輸出 N 行，缺失等級輸出 0。