Codeforces 61E Enemy is weak：樹狀數組計算三元組逆序數

題目

給定長度 n (n ≤ 2×10^5) 的排列，求三元組 (i,j,k) 滿足 i a[j] > a[k] 的個數。即每個元素左邊有多少個比它大、右邊有多少個比它小，乘積求和。

樹狀數組 (BIT) 雙遍歷

1. 值域壓縮：將排列值映射到 1..n (按大小排序排名)。
2. 左向遍歷：leftGreater[i] = 已插入元素中 > a[i] 的個數 = i-1 - query(rank[i])。插入 rank[i]。
3. 右向遍歷：rightSmaller[i] = 未插入元素中 < a[i] 的個數 = query(rank[i]-1)。插入 rank[i]。
4. 答案 = Σ leftGreater[i] * rightSmaller[i] (64 位)。

代碼框架

struct Node { int val, idx; } a[MAXN];
int bit[MAXN], rank[MAXN];
long long leftG[MAXN], rightS[MAXN];

void add(int i, int v) { for (; i<=n; i+=i&-i) bit[i] += v; }
int sum(int i) { int s=0; for(;i>0;i-=i&-i) s+=bit[i]; return s; }

int main() {
    cin >> n;
    for (int i=1;i<=n;++i) { cin>>a[i].val; a[i].idx=i; }
    sort(a+1, a+n+1, [](Node x, Node y){ return x.val=1;--i) {
        rightS[i] = sum(rank[i]-1);
        add(rank[i], 1);
    }
    long long ans = 0;
    for (int i=1;i<=n;++i) ans += leftG[i] * rightS[i];
    cout << ans << '\n';
}

複雜度

• 時間：O(n log n) —— 排序 + 2n 次 BIT 操作
• 空間：O(n)

關鍵點

• 答案可能達 C(n,3) ≈ 10^15，必須用 long long。
• 值域壓縮保證 BIT 大小為 n。
• 左右遍歷邏輯對稱，注意查詢邊界 (rank[i]-1 為嚴格小於)。