HDU 5147 Sequence II：樹狀數組統計三元組逆序對

問題建模

給定排列 a[1..N]，求三元組 (i, j, k) 數量，滿足 i < j < k 且 a[i] < a[j] > a[k]。即以 j 為峰值的「山形」三元組。

樹狀數組應用

預處理每個位置作為「峰」的左側較小元素數 lef[j] 和右側較小元素數 rig[j]：

• 正序遍歷，用 BIT 統計 lef[j] = query(a[j])
• rig[j] = (N - j) - (a[j] - 1 - lef[j]) 通過補集計算

計算答案

枚舉中間位置 j，以 j 為峰的三元組數為 lef[j] * (sum_{k>j} rig[k])。反序遍歷累加 rig 後綴和即可 O(N) 完成。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
int N, a[MAXN], bit[MAXN], lef[MAXN], rig[MAXN];

inline int lowbit(int x) { return x & -x; }
void add(int x, int v) { for (; x <= N; x += lowbit(x)) bit[x] += v; }
int sum(int x) { int r = 0; for (; x; x -= lowbit(x)) r += bit[x]; return r; }

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        fill(bit, bit + N + 1, 0);
        for (int i = 1; i <= N; ++i) scanf("%d", &a[i]);
        long long ans = 0, suffix = 0;
        for (int i = 1; i <= N; ++i) {
            lef[i] = sum(a[i]);
            rig[i] = N - i - a[i] + lef[i] + 1;
            add(a[i], 1);
            suffix += rig[i];
        }
        for (int i = 1; i <= N; ++i) {
            suffix -= rig[i];
            ans += suffix * lef[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度

• 時間：O(N log N) 每測試用例
• 空間：O(N)

本題展示了 BIT 在區間統計中的靈活應用，關鍵在於將三元組計數分解為左右獨立部分，再通過後綴和優化枚舉。