POJ 2352 Stars：線段樹統計左下方星星數

POJ 2352 Stars：線段樹單點更新求逆序對變體

題目大意：給定 N (≤15000) 個星星坐標，已按 y 升序、x 升序排列。每顆星星的「等級」定義為其左下方（x' ≤ x 且 y' ≤ y）星星數量。輸出每個等級的星星個數。

解題思路

因輸入已按 y 排序，處理到第 i 顆星星時，前面所有星星的 y 坐標均 ≤ 當前 y。只需統計 x 坐標 ≤ 當前 x 的星星數。將 x 坐標作為線段樹下標（範圍 0~32000），每插入一顆星星先查詢 [0, x] 區間和（即其等級），再單點更新 +1。最後統計各等級頻次。

核心代碼

const int MAXX = 32000;
int sum[MAXX * 4 + 10];
int levelCnt[15010];

void update(int rt, int l, int r, int pos) {
    if (l == r) { sum[rt]++; return; }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(rt<<1, l, mid, pos);
    else update(rt<<1|1, mid+1, r, pos);
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

int query(int rt, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) return 0;
    if (ql <= l && r <= qr) return sum[rt];
    int mid = (l + r) >> 1;
    return query(rt<<1, l, mid, ql, qr) + query(rt<<1|1, mid+1, r, ql, qr);
}

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int x, y; scanf("%d%d", &x, &y);
        int lv = query(1, 0, MAXX, 0, x);
        levelCnt[lv]++;
        update(1, 0, MAXX, x);
    }
    for (int i = 0; i < n; i++) printf("%d\n", levelCnt[i]);
    return 0;
}

優化提示

• 輸入量大，必須用 scanf 而非 cin。
• 線段樹大小 4 * 32001 足夠。
• 等級最大為 N-1，開數組 levelCnt[N] 統計即可。