Codeforces 261D：樹狀數組統計逆序對變體

Codeforces Round #261 Div.2 D：樹狀數組應用

給定長度為 n 的序列 a，定義 f(l, r, x) 為區間 [l, r] 中等於 x 的元素個數。求滿足 i < j 且 f(1, i, a[i]) > f(j, n, a[j]) 的數對 (i, j) 數量。

解題思路

預處理每個位置 i 的前綴計數 f1[i] = f(1, i, a[i]) 和後綴計數 f2[i] = f(i, n, a[i])。問題轉化為：求 i < j 且 f1[i] > f2[j] 的數對數。這是經典的逆序對問題，可用樹狀數組（Fenwick Tree）解決。

正向遍歷將 f1[i] 加入樹狀數組，反向遍歷時先移除 f1[i]，查詢大於 f2[i] 的個數並累加答案。

代碼實現

int n; int aa[1000000 + 55]; int bb[1000000 + 55]; int c[1000000 + 55];
map<int, int> mp;
ll lowbit(ll x) { return x & (-x); }
void add(int i, int val) { while (i <= n) { c[i] += val; i += lowbit(i); } }
ll get_sum(int i) { ll sum = 0; while (i) { sum += c[i]; i -= lowbit(i); } return sum; }
void init() { memset(c, 0, sizeof(c)); memset(aa, 0, sizeof(aa)); memset(bb, 0, sizeof(bb)); mp.clear(); }
int main() {
    while (scanf("%d", &n) == 1) {
        init();
        for (int i = 1; i <= n; i++) scanf("%d", &aa[i]);
        for (int i = 1; i <= n; i++) { mp[aa[i]]++; bb[i] = mp[aa[i]]; add(bb[i], 1); }
        mp.clear(); ll ans = 0;
        for (int i = n; i >= 1; i--) {
            add(bb[i], -1); mp[aa[i]]++; int tmp = mp[aa[i]];
            ans += i - get_sum(tmp) - 1;
        }
        cout << ans << endl;
    }
    return 0;
}

時間複雜度 O(n log n)，空間 O(n)，充分利用樹狀數組的前綴和特性。