POJ 2481 Cows：區間包含關係與樹狀數組離散化解法

編輯：關於C語言

問題描述

農夫約翰的 N 隻奶牛各自偏好一段草地區間 [S, E]。若牛 i 的區間 [Si, Ei] 完全包含牛 j 的區間 [Sj, Ej]（即 Si ≤ Sj 且 Ej ≤ Ei，且區間長度嚴格大於），則稱牛 i 比牛 j 強。請對每隻奶牛，計算有多少隻奶牛比它強。輸入包含多組測試數據，N ≤ 10^5，坐標範圍 0 ≤ S < E ≤ 10^5，以 0 結束輸入。

核心思路：幾何轉化與樹狀數組

將每個區間 [S, E] 視為二維平面上的點 (S, E)。條件「Si ≤ Sj 且 Ej ≤ Ei」等價於：點 i 在點 j 的左上方（x 坐標較小，y 坐標較大）。因此，問題轉化為：對每個點，統計其左上方有多少個點。這正是經典問題 HDU 1541 Stars（統計左下方點數）的變形。

排序策略

Stars 題中點已按 y 升序、x 升序給出，直接用樹狀數組維護 x 坐標前綴和。本題點無序，需自行排序：

先按 y（即 E）從大到小排序，保證處理到某點時，所有 y 更大的點已加入樹狀數組。
y 相同時，按 x（即 S）從小到大排序，確保同 y 下 x 較小的點先被查詢，避免將同 y 且 x 相等的點誤算為「更強」。

處理相同區間

題目要求「S 和 E 相同不計在內」。排序後相同區間相鄰，查詢時若發現與前一個點坐標完全相同，直接沿用前一個點的查詢結果，不重複更新樹狀數組（或更新後再查詢下一個），從而排除相同區間互相計數。

坐標離散化

坐標上限 10^5，加上樹狀數組下標從 1 開始，需將所有 S、E 統一 +1 避免 0 下標；若坐標範圍更大則需離散化壓縮。

算法流程

讀入 N，存儲每個區間的 S、E、原始索引 id。
所有 S、E 同時 +1（應對 0 值）。
按 y 降序、x 升序排序。
初始化樹狀數組。
遍歷排序後的點：
- 若與前一點 (x,y) 相同，val[id] = val[prev_id]；
- 否則 val[id] = query(x)（查詢 x 前綴和，即當前已加入點中 x 坐標 ≤ 當前 x 的個數，對應左上方點數）。
- update(x, 1) 將當前點加入樹狀數組。
按原始 id 順序輸出 val[0..N-1]。

關鍵代碼解析

struct node { int x, y, id; } a[100005];
int n, bit[100005], ans[100005];

bool cmp(node a, node b) {
    if (a.y != b.y) return a.y > b.y; // y 降序
    return a.x < b.x;                   // x 升序
}

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

void update(int i, int v) {
    for (; i <= 100005; i += lowbit(i)) bit[i] += v;
}

int query(int i) {
    int s = 0;
    for (; i > 0; i -= lowbit(i)) s += bit[i];
    return s;
}

int main() {
    while (scanf("%d", &n), n) {
        memset(bit, 0, sizeof(bit));
        for (int i = 0; i < n; ++i) {
            scanf("%d%d", &a[i].x, &a[i].y);
            a[i].id = i;
            ++a[i].x; ++a[i].y; // 離散化/避免 0
        }
        sort(a, a + n, cmp);
        ans[a[0].id] = query(a[0].x);
        update(a[0].x, 1);
        for (int i = 1; i < n; ++i) {
            if (a[i].x == a[i-1].x && a[i].y == a[i-1].y)
                ans[a[i].id] = ans[a[i-1].id];
            else
                ans[a[i].id] = query(a[i].x);
            update(a[i].x, 1);
        }
        for (int i = 0; i < n; ++i) {
            if (i) printf(" ");
            printf("%d", ans[i]);
        }
        puts("");
    }
    return 0;
}