問題描述

N 個點（星星），座標 (X,Y)，0≤X,Y≤32000。點按 Y 升序輸入，Y 相同時按 X 升序。定義點的「等級」為：左下方（X'≤X 且 Y'≤Y）包含的點數（不含自身）。輸出每個等級 0~N-1 的點個數。

關鍵洞察

• 輸入已按 Y 排序 → 處理到第 i 個點時，所有 Y' < Y_i 的點已處理完畢，Y' = Y_i 且 X' < X_i 的點也已處理（因同 Y 按 X 升序）。
• 因此，當前點的左下方點 = 已處理點中 X' ≤ X_i 的個數。
• 只需一維樹狀數組維護 X 軸頻率，單點更新、前綴和查詢均 O(log MAXX)。

算法流程

1. 初始化 BIT 大小 32001（座標 0~32000，內部 1-based 索引）。
2. 遍歷每個點 (x,y)：
   查詢 sum(x+1) 得到等級（x 從 0 開始，BIT 索引 +1）。
   更新 add(x+1, 1)。
   統計 level_cnt[level]++。
3. 輸出 level_cnt[0..N-1]。

代碼實現

#include <cstdio>
#include <cstring>
const int MAXX = 32001;
int bit[MAXX], level_cnt[15005];

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

void add(int idx, int val) {
    for (; idx < MAXX; idx += lowbit(idx)) bit[idx] += val;
}

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

int main() {
    int n;
    while (~scanf("%d", &n)) {
        memset(bit, 0, sizeof(bit));
        memset(level_cnt, 0, sizeof(level_cnt));
        for (int i = 0; i < n; ++i) {
            int x, y; scanf("%d%d", &x, &y);
            int level = sum(x + 1); // x 0-based -> BIT 1-based
            level_cnt[level]++;
            add(x + 1, 1);
        }
        for (int i = 0; i < n; ++i) printf("%d\n", level_cnt[i]);
    }
    return 0;
}

關鍵細節

1. 座標映射：X ∈ [0,32000] → BIT 索引 1~32001，數組開 32002 或 32005。
2. 輸入量大：必須用 scanf，關閉同步 ios::sync_with_stdio(false)。
3. 多測試用例：每案例重置 BIT 與 level_cnt。
4. 等級範圍：0 ~ N-1，輸出 N 行。

複雜度

• 時間：O(N log MAXX)，N≤15000，MAXX=32001，約 15000×15 ≈ 22.5萬操作，極快。
• 空間：O(MAXX) ≈ 128KB。

總結

POJ 2352 是「二維偏序 + 離線處理 + 一維 BIT」的教科書級應用。輸入順序滿足 Y 排序，將二維問題降維為一維前綴和。掌握「排序 + BIT」模板，可解決大量「左下方/左上方/右下方點計數」類問題。關鍵點：座標 0-based 轉 1-based、BIT 尺寸、輸入輸出優化。