題目：N (≤10⁵) 條區間 [S, E]（0≤Si 比牛 j 強：S_i ≤ S_j 且 E_j ≤ E_i 且 (E_i-S_i) > (E_j-S_j)。即 i 的區間嚴格包含 j 的區間。對每頭牛，輸出比它強的牛的數量。
將區間按 右端點 E 降序，E 相同則按 左端點 S 升序 排序。
此時，對於當前區間 [S, E]，排在它前面的區間滿足：E' ≥ E，且若 E'=E 則 S' ≤ S。
要找「嚴格包含」當前區間的牛，只需在已處理區間中統計 S' ≤ S 的數量（若 E'=E 且 S'=S 則不算嚴格包含，需去重）。
id。E 降序，S 升序。sum(S)（已處理區間中 S' ≤ S 的個數）。E,S 完全相同，答案 = 前一區間答案（去重）。add(S, 1)。ans[id]。ans。座標 S ∈ [0, 10⁵]，需 +1 避開 0 索引。
add(x, v)：for(; x
sum(x)：for(; x>0; x-=x&-x) res+=bit[x];
#include <bits/stdc++.h>
using namespace std;
const int MAXC = 100005;
struct Interval { int s, e, id; };
int bit[MAXC+2], ans[100005];
Interval a[100005];
void add(int x, int v) { for (; x <= MAXC; x += x&-x) bit[x] += v; }
int sum(int x) { int r=0; for(; x>0; x-=x&-x) r+=bit[x]; return r; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
while (cin >> n && n) {
for (int i = 1; i <= n; ++i) {
cin >> a[i].s >> a[i].e;
a[i].id = i;
++a[i].s; ++a[i].e; // 座標壓縮/避開0
}
sort(a+1, a+n+1, [](const Interval& x, const Interval& y){
if (x.e != y.e) return x.e > y.e;
return x.s < y.s;
});
fill(bit, bit+MAXC+2, 0);
for (int i = 1; i <= n; ++i) {
int cnt = sum(a[i].s);
if (i>1 && a[i].e==a[i-1].e && a[i].s==a[i-1].s)
cnt = ans[a[i-1].id]; // 相同區間去重
ans[a[i].id] = cnt;
add(a[i].s, 1);
}
for (int i = 1; i <= n; ++i) {
if (i>1) cout << ' ';
cout << ans[i];
}
cout << '\n';
}
return 0;
}
E 降序，S 升序 將「嚴格包含」轉化為「前綴查詢」。O(log C) 單點更新、前綴查詢。S,E 可能為 0，樹狀數組下標從 1 開始，統一 +1。| 指標 | 複雜度 | 說明 |
|---|---|---|
| 時間 | O(N log C) | 排序 O(N log N) + N 次 BIT 操作 |
| 空間 | O(C + N) | BIT 陣列 + 區間存儲 |
POJ 2481 是「區間包含關係 + 樹狀數組」的教科書級應用。它展示了如何通過巧妙排序將二維偏序問題（S_i ≤ S_j, E_j ≤ E_i）轉化為一維前綴和查詢。此模式廣泛適用於「矩形包含、點支配、版本控制」等偏序統計問題。
