您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

Codeforces 12D Ball：樹狀數組解決三元素排序問題

編輯：C++ 入門

問題背景與核心思路

Codeforces 12D "Ball" 是一道經典的算法題，要求對三個屬性進行排序並統計滿足特定條件的三元組數量。題目給定 n 個球，每個球擁有三個屬性值 (b[0], b[1], b[2])，需要找出滿足 b[0] 遞增、b[1] 遞減、b[2] 遞增的三元組數量。這是一個典型的三維偏序問題，通過排序降維配合樹狀數組（Fenwick Tree）可在 O(n log n) 時間內解決。

算法步驟詳解

1. 首維排序與離散化

首先按第一屬性 b[0] 升序排序，將相同 b[0] 的元素分為同一組並分配相同的排名（num）。這將第一維轉化為離散的整數排名，範圍為 [1, rank]，其中 rank ≤ n。這一步消除了第一維的影響，問題轉化為在二維平面上尋找滿足條件的點對。

2. 次維排序與分組處理

接著按第二屬性 b[1] 降序排序。這樣在處理過程中，已經處理過的元素其 b[1] 均大於等於當前元素。為了避免同組內元素互相影響，採用「先查詢後更新」的策略：對於相同 b[1] 的元素，先全部查詢樹狀數組，再全部更新。這確保了同一 b[1] 值的元素不會互相計數。

3. 樹狀數組維護第三維最大值

樹狀數組 c[i] 維護的是：排名為 i 的元素中，第三屬性 b[2] 的最大值。查詢操作 maxx(pos) 返回排名大於 pos 的所有元素中 b[2] 的最大值。若該最大值大於當前元素的 b[2]，則存在滿足條件的三元組，答案加一。更新操作 change(pos, val) 將排名 pos 位置的最大值更新為 val。

關鍵代碼實現

#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int n, c[N], maxn;
struct Node { int b[3], num; } w[N];

inline int lowbit(int x) { return x & (-x); }

void change(int pos, int val) {
    while (pos) c[pos] = max(c[pos], val), pos -= lowbit(pos);
}

int query(int pos) {
    int ans = -1;
    while (pos <= maxn) ans = max(ans, c[pos]), pos += lowbit(pos);
    return ans;
}

bool cmp0(Node x, Node y) { return x.b[0] < y.b[0]; }
bool cmp1(Node x, Node y) { return x.b[1] > y.b[1]; }

int main() {
    while (cin >> n) {
        for (int i = 0; i < n; ++i) scanf("%d", &w[i].b[0]);
        for (int i = 0; i < n; ++i) scanf("%d", &w[i].b[1]);
        for (int i = 0; i < n; ++i) scanf("%d", &w[i].b[2]);
        
        sort(w, w + n, cmp0);
        int rank = 1; w[0].num = 1;
        for (int i = 1; i < n; ++i)
            w[i].num = (w[i].b[0] == w[i-1].b[0]) ? rank : ++rank;
        
        sort(w, w + n, cmp1);
        fill(c + 1, c + rank + 1, -1);
        maxn = rank;
        
        long long ans = 0;
        for (int i = 0, j; i < n; i = j) {
            for (j = i; j < n && w[i].b[1] == w[j].b[1]; ++j)
                if (query(w[j].num + 1) > w[j].b[2]) ++ans;
            for (j = i; j < n && w[i].b[1] == w[j].b[1]; ++j)
                change(w[j].num, w[j].b[2]);
        }
        cout << ans << endl;
    }
    return 0;
}