POJ 2352 Stars：樹狀數組統計二維偏序（星星等級）

問題描述

給定 N ≤ 15000 顆星星的坐標 (x, y)，0 ≤ x,y ≤ 32000。星星按 y 升序、x 升序輸入。定義星星等級 = 坐標左下方（x' ≤ x 且 y' ≤ y）的星星數。輸出每個等級（0 到 N-1）的星星個數。

核心思路：樹狀數組 (Fenwick Tree) 維護 x 軸前綴和

因輸入已按 y 排序，處理第 i 顆星星時，所有 y' ≤ y_i 的星星已處理完畢。只需查詢 x ≤ x_i 的已處理星星數，即為其等級。用樹狀數組維护 x 軸頻率，單點更新、前綴和查詢均 O(log X)。

算法流程

1. 初始化樹狀數組 bit[32001]（x 從 1 開始，輸入 x 可能為 0，需 +1）。
2. 讀入每顆星星 (x, y)：
3. level = query(x + 1)（查詢 ≤ x 的個數）。
4. ans[level]++。
5. add(x + 1, 1)（將當前星星加入樹狀數組）。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXX = 32005;
int bit[MAXX];
int ans[15005];

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

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

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;
            int level = query(x + 1);  // x 從 0 開始，樹狀數組從 1 開始
            ans[level]++;
            add(x + 1, 1);
        }
        for (int i = 0; i < N; ++i) cout << ans[i] << '\n';
    }
    return 0;
}

複雜度

時間 O(N log X) ≈ 15000 × 15 ≈ 2.25×10⁵，空間 O(X) = 32005。極快。

關鍵點

1. 輸入順序保證 y 非遞減，將二維偏序轉化為一維前綴和。
2. x 範圍 0~32000，樹狀數組大小 32001+5，下標 +1 處理 0 值。
3. ans 數組大小 N，等級最大為 N-1。