POJ 2352 Stars：樹狀數組統計星星等級

POJ 2352 Stars：Fenwick Tree 計算左下方星星數

題目大意

N ≤ 15000 顆星，座標 (X,Y)，Y 已按升序輸入（同 Y 按 X 升序）。星星等級 = 左下方（x' ≤ x 且 y' ≤ y）星星數。求各等級星星個數分布。

關鍵觀察

因 Y 已排序，處理第 i 顆星時，所有 y' ≤ yᵢ 的星已處理完畢。只需統計已處理星中 x' ≤ xᵢ 的個數 → 樹狀數組維護 X 座標頻率。

座標處理

X ∈ [0, 32000]，樹狀數組下標從 1 起，將 X 整體 +1 避免 0 下標。

代碼

#include 
using namespace std;
const int MAXX = 320001;
int c[MAXX], ans[15005];
int lowbit(int x) { return x & -x; }
void add(int x) { for (; x0;x-=lowbit(x)) r+=c[x]; return r; }
int main() {
    int n; while (scanf("%d",&n)!=EOF) {
        memset(c,0,sizeof(c)); memset(ans,0,sizeof(ans));
        for (int i=0,x,y;i