POJ 2481 Cows：樹狀數組解區間包含計數

題目大意

N 條區間 [S,E]，若區間 i 完全包含區間 j 且長度更長，則 i 比 j 強。求每條區間有多少條比它強的區間。N ≤ 10⁵，坐標 ≤ 10⁵。

排序 + BIT

按右端點 E 從大到小排序（E 相同則 S 從小到大）。此時已處理的區間 E 均 ≥ 當前 E。對於當前區間 [S,E]，比它強的區間必須滿足 S' ≤ S 且 E' ≥ E（已滿足），且長度更長（E'-S' > E-S）。因排序保證 E' ≥ E，只需統計 S' ≤ S 的數量，用樹狀數組維護 S 坐標頻次。

去重處理

相同 [S,E] 的區間答案相同，直接複製前一個答案，避免重複計算。

代碼框架

sort(cows, cows+n, [](a,b){ return a.e!=b.e ? a.e>b.e : a.s0 and cows[i]==cows[i-1]: ans[id]=ans[prev_id]
    else: ans[id] = bit.query(cows[i].s+1)
    bit.add(cows[i].s+1, 1)

複雜度

排序 O(N log N)，BIT 操作 O(log MaxCoord)，總 O(N log N)，空間 O(MaxCoord)。

總結

經典「離線+排序+樹狀數組」套路，將二維偏序問題轉化為一維前綴和，配合去重技巧，代碼短小精悍。