Codeforces 12D Ball：三維屬性支配與樹狀數組優化

題目背景

有 N 位貴婦，每位擁有美貌 B_i、智力 I_i、財富 R_i。若存在另一貴婦在三項屬性上均嚴格大於她，則該貴婦為「潛在自殺者」。求這類貴婦的數量。
限制：N ≤ 500,000，屬性值 ≤ 10⁹。

解題思路

1. 按美貌 B 升序排序，相同 B 者按智力 I 降序，再按財富 R 降序（確保同組內不互相支配）。
2. 離散化智力 I，將其映射到 [1, M]。
3. 使用樹狀數組（Fenwick Tree）維护後綴最大財富：tree[x] 表示智力排名 ≥ x 的最大 R。
4. 遍歷排序後的貴婦，分組處理相同 B 的區間：先查詢當前 I 排名後的最大 R，若大於當前 R 則為自殺者；再批量更新該組的 R 到樹狀數組。

關鍵代碼片段

struct Lady { int b, i, r, id; };
bool cmp(const Lady& a, const Lady& b) {
    if (a.b != b.b) return a.b < b.b;
    if (a.i != b.i) return a.i > b.i;
    return a.r > b.r;
}

// 離散化 I
vector<int> all_i;
for (auto& l : ladies) all_i.push_back(l.i);
sort(all_i.begin(), all_i.end());
all_i.erase(unique(all_i.begin(), all_i.end()), all_i.end());
for (auto& l : ladies) l.i = lower_bound(all_i.begin(), all_i.end(), l.i) - all_i.begin() + 1;

// 樹狀數組：後綴最大值
void update(int pos, int val) {
    for (; pos > 0; pos -= pos & -pos) tree[pos] = max(tree[pos], val);
}
int query(int pos) {
    int res = -1;
    for (; pos <= max_i; pos += pos & -pos) res = max(res, tree[pos]);
    return res;
}

// 主循環
int ans = 0;
for (int l = 0, r; l < n; l = r) {
    r = l;
    while (r < n && ladies[r].b == ladies[l].b) ++r;
    for (int k = l; k < r; ++k)
        if (query(ladies[k].i + 1) > ladies[k].r) ++ans;
    for (int k = l; k < r; ++k)
        update(ladies[k].i, ladies[k].r);
}

複雜度

• 排序 + 離散化：O(N log N)
• 樹狀數組操作：O(N log N)
• 總體 O(N log N)，滿足 50 萬數據規模。