POJ 2481 Cows：樹狀數組解決區間包含關係計數問題

問題轉化

每頭牛對應區間 [S, E]。牛 i 比牛 j 強 ⇔ S_i ≤ S_j 且 E_j ≤ E_i 且長度更長。等價於：區間 i **嚴格包含** 區間 j。
求每個區間被多少其他區間嚴格包含。

排序策略

按右端點 E **降序**，右端點相同按左端點 S **升序**。
遍歷過程中，當前區間的右端點 ≤ 已處理區間的右端點。只需統計已處理區間中左端點 ≤ 當前 S 的個數，即為包含當前區間的數量。

樹狀數組（BIT）實現

• 坐標範圍 [0, 1e5]，直接用作 BIT 索引（+1 避免 0）。
• add(S+1, 1) 表示插入一個左端點為 S 的區間。
• query(S+1) 返回左端點 ≤ S 的區間數。

去重處理

相同區間 [S, E] 答案相同。排序後若 a[i] == a[i-1]，直接複製答案，避免重複計算。

關鍵代碼

struct Node { int l, r, id; };
bool cmp(Node a, Node b) {
    if (a.r != b.r) return a.r > b.r; // 右端點降序
    return a.l < b.l;                  // 左端點升序
}

int main() {
    while (cin >> n, n) {
        for (i=1; i<=n; ++i) cin >> a[i].l >> a[i].r, a[i].id=i;
        sort(a+1, a+n+1, cmp);
        memset(c, 0, sizeof c);
        for (i=1; i<=n; ++i) {
            if (i>1 && a[i].l==a[i-1].l && a[i].r==a[i-1].r)
                ans[a[i].id] = ans[a[i-1].id];
            else
                ans[a[i].id] = query(a[i].l + 1);
            add(a[i].l + 1, 1);
        }
        // 輸出 ans[1..n]
    }
}

複雜度

排序 O(N log N)，BIT 操作 O(log MAXC)，總 O(N log N)，N ≤ 1e5 輕鬆通過。