HDU 4000 / HRBUST 1625 - ikki 的數字：樹狀數組統計排列中特定三元組

題目背景與敘述

ikki 近來對數字產生濃厚興趣。他在紙上寫下連續的 N 個數字，這些數字構成 1 到 N 的一個排列（即每個數字在 [1, N] 之間且不重複），下標從 1 到 N。現在他想考考你：在這 N 個數字中，能找出多少個三個數的組合 (x, y, z)，滿足 num[x] < num[z] < num[y] 且 x < y < z？

輸入輸出格式

輸入包含多組測試資料。第一行為整數 T 表示測試組數。每組資料第一行輸入 N (1 ≤ N ≤ 5000)，第二行輸入 N 個整數表示 1~N 的一個排列。對於每組資料，輸出 Case #k: p，其中 k 為測試案例編號（從 1 開始），p 為滿足條件的三元組數量，結果需對 100000007 取模。

樣例

Sample Input
2
6
1 3 2 6 5 4
5
3 5 2 4 1

Sample Output
Case #1: 10
Case #2: 1

解題思路：樹狀數組 + 組合數學

核心目標是統計滿足 i < j < k 且 a[i] < a[k] < a[j] 的三元組總數。直接三層迴圈枚舉複雜度 O(N³) 顯然不可行（N ≤ 5000）。觀察條件可知，a[k] 扮演「中間值」的角色：它比左邊某數大、比右邊某數小。

我們可以對每個位置 k 作為「中間元素」進行貢獻計算。利用樹狀數組（Fenwick Tree）維護前綴頻次，可在 O(log N) 內查詢某值左側比它小/大的個數。具體步驟：

1. 遍歷序列，對於當前元素 val = a[i]，查詢前面比它小的個數 preSmaller，則前面比它大的個數 preBigger = i - 1 - preSmaller。
2. 整個序列中比 val 大的總數 totBigger = N - val，故右側比它大的個數 afterBigger = totBigger - preBigger。
3. 若 afterBigger ≥ 2，從這些右側較大元素中任選兩個與當前元素組合，即可形成 a[i] < a[k] < a[j] 型三元組，數量為 C(afterBigger, 2)。
4. 但上述包含了 a[i] < a[j] < a[k] 型（即右側兩大元素還保持遞增）的非法情況，需減去。這部分等價於：對於每個右側較大元素作為「中間值」，其左側（含當前）比它小的個數之和。經推導，總非法數 = preSmaller * afterBigger。
5. 因此，以當前元素為「中間值」的合法貢獻 = C(afterBigger, 2) - preSmaller * afterBigger。累加所有位置即得答案。

參考代碼 (C++)

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int MOD = 100000007;
int T, n;
int c[5010];

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

LL getsum(int x) {
    LL sum = 0;
    while (x > 0) {
        sum += c[x];
        x -= lowbit(x);
    }
    return sum;
}

void update(int x, int val) {
    while (x <= n) {
        c[x] += val;
        x += lowbit(x);
    }
}

int main() {
    cin >> T;
    int Case = 1;
    while (T--) {
        memset(c, 0, sizeof(c));
        cin >> n;
        LL ans = 0;
        for (int i = 1; i <= n; i++) {
            int temp; cin >> temp;
            update(temp, 1);
            LL preSmaller = getsum(temp - 1);
            LL preBigger = i - 1 - preSmaller;
            LL totBigger = n - temp;
            LL afterBigger = totBigger - preBigger;
            ans -= preSmaller * afterBigger;
            if (afterBigger >= 2) {
                ans += afterBigger * (afterBigger - 1) / 2;
            }
            ans %= MOD;
            if (ans < 0) ans += MOD;
        }
        cout << "Case #" << Case++ << ": " << ans << endl;
    }
    return 0;
}

複雜度分析

每個測試案例需遍歷 N 個元素，每次進行 O(log N) 的樹狀數組操作，總時間複雜度 O(N log N)，空間複雜度 O(N)，完全滿足 N ≤ 5000 的限制。