POJ 2352 Stars：星星等級統計 (線段樹 / BIT)

問題描述

給定 N 顆星星的座標 (X, Y)（0 ≤ X,Y ≤ 32000，1 ≤ N ≤ 15000）。星星按 Y 升序、同 Y 按 X 升序輸入。一顆星的「等級」定義為：左下方（含同行左側）星星數。即 x' ≤ x 且 y' ≤ y 的星星數（不含自身）。輸出每個等級 0..N-1 的星星個數。

解題思路：線段樹維護 X 軸頻次

因輸入已按 Y 排序，掃描過程中所有已處理星星的 Y' ≤ Y 自動滿足。只需查詢「X' ≤ X 的已處理星星數」。

1. 離散化或直接用 X 範圍（0..32000）建線段樹 / BIT（Fenwick Tree）。
2. 遍歷星星：對每顆 (x, y)，查詢 sum(0, x) → 即其等級 level。ans[level]++。然後 add(x, 1) 更新樹。
3. 最後輸出 ans[0]..ans[N-1]。

關鍵代碼片段 (C++ BIT 版)

#include <bits/stdc++.h>
using namespace std;
const int MAXX = 32001;
const int MAXN = 15005;

int bit[MAXX];
int ans[MAXN];

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    while (cin >> N) {
        fill(bit, bit+MAXX, 0);
        fill(ans, ans+N, 0);
        for (int i = 0; i < N; ++i) {
            int x, y; cin >> x >> y;
            ++x;  // BIT 1-based
            int level = sum(x);
            ans[level]++;
            add(x, 1);
        }
        for (int i = 0; i < N; ++i) cout << ans[i] << '\n';
    }
    return 0;
}

複雜度分析

• BIT 操作 O(log X)，X ≤ 32001 → log X ≈ 15。
• 總時間 O(N log X) ≈ 2.2×10^5，空間 O(X + N)。
• 輸入量大，建議用 scanf/fast I/O。

總結

POJ 2352 是典型的「二維偏序統計」問題，利用輸入已按一維排序的特性，退化為一維頻次統計。BIT（Fenwick Tree）代碼極短、常數極小，是此類問題的首選資料結構。關鍵在於識別「等級 = 左下方點數」等價於「已處理點中 X' ≤ X 的個數」。