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

題目大意

給定 N（≤100,000）個區間 [l, r]，對每個區間求：有多少個其他區間完全包含它（即 l_j ≤ l_i 且 r_j ≥ r_i，允許邊界重合）。

核心思路：排序 + 樹狀數組

1. 區間按 l 升序、r 降序排序。如此遍歷時，當前區間之前的區間必滿足 l_j ≤ l_i。
2. 需統計之前區間中 r_j ≥ r_i 的個數。用樹狀數組維护右端點頻次，查詢區間 [r_i, MAX] 的和。
3. 相同區間（l、r 均相同）視為同一組，答案相同，僅更新一次樹狀數組但查詢多次共享結果。

算法流程

sort(segments, key=(l ASC, r DESC));
for seg in segments:
    if same as previous:
        ans[seg.id] = ans[prev.id];
    else:
        ans[seg.id] = query(MAX) - query(seg.r - 1); // 統計 r_j >= r_i
    add(seg.r, 1);

關鍵細節

• 右端點範圍 ≤ 100,000，直接作為樹狀數組下標，無需離散化。
• 排序規則確保：同 l 時，大 r 先處理，避免同組區間互相計數（因大 r 不包含小 r）。
• 相同區間共享答案，避免重複查詢導致自我計數。

複雜度

• 排序：O(N log N)
• 每區間一次查詢+更新：O(log MAX)
• 總時間：O(N log N)，空間：O(MAX)，完美應對 100,000 規模。

參考代碼片段

struct Seg { int l, r, id; };
bool operator<(Seg a, Seg b) {
    if (a.l != b.l) return a.l < b.l;
    return a.r > b.r;
}
void add(int x, int v) { for(; x<=MAXN; x+=x&-x) bit[x]+=v; }
int sum(int x) { int r=0; for(; x; x-=x&-x) r+=bit[x]; return r; }
// 主循環
for (int i=1; i<=N; ++i) {
    if (i>1 && s[i].l==s[i-1].l && s[i].r==s[i-1].r)
        ans[s[i].id] = ans[s[i-1].id];
    else
        ans[s[i].id] = sum(MAXN) - sum(s[i].r-1);
    add(s[i].r, 1);
}