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

POJ 1990 MooFest 詳解：樹狀數組優化雙向貢獻計算聲音總和

編輯：關於C++

題目大意

N 頭牛（N ≤ 20,000）站在數軸上（位置 1..20,000），每牛有聽力閾值 v[i]。任意兩牛 i,j 對話音量 = |x[i]-x[j]| * max(v[i], v[j])。求所有牛對音量之和。

核心思路：按閾值排序 + 樹狀數組維護座標統計

按 v 升序處理牛。處理第 i 牛時，之前牛的 v 均 ≤ 當前 v[i]，故雙向貢獻公式統一為：

貢獻 = v[i] * ( Σ|x[i] - x[j]| )，其中 j 為已處理牛。

絕對值和拆解

設已處理牛座標集合為 S，x[i] 為當前座標：

Σ_{j∈S} |x[i] - x[j]| = (cntL * x[i] - sumL) + (sumR - cntR * x[i])

cntL, sumL：座標 ≤ x[i] 的牛數與座標和
cntR, sumR：座標 > x[i] 的牛數與座標和

兩個樹狀數組維護：BIT1 存牛數，BIT2 存座標和。

完整代碼

#include 
using namespace std;
using ll = long long;
const int MAXX = 20000;

struct Cow { int v, x; };
Cow cows[20005];
ll bitCnt[MAXX+5], bitSum[MAXX+5];

void add(ll bit[], int idx, ll val) {
    for (; idx <= MAXX; idx += idx & -idx) bit[idx] += val;
}
ll query(ll bit[], int idx) {
    ll res = 0;
    for (; idx; idx -= idx & -idx) res += bit[idx];
    return res;
}

int main() {
    int n; scanf("%d", &n);
    for (int i=1; i<=n; ++i) scanf("%d%d", &cows[i].v, &cows[i].x);
    sort(cows+1, cows+n+1, [](Cow a, Cow b){ return a.v < b.v; });
    
    ll ans = 0;
    for (int i=1; i<=n; ++i) {
        int x = cows[i].x;
        ll v = cows[i].v;
        
        ll cntL = query(bitCnt, x);
        ll sumL = query(bitSum, x);
        ll cntR = (i-1) - cntL;
        ll sumR = query(bitSum, MAXX) - sumL;
        
        ll contrib = v * (cntL * x - sumL + sumR - cntR * x);
        ans += contrib;
        
        add(bitCnt, x, 1);
        add(bitSum, x, x);
    }
    printf("%lld\n", ans);
    return 0;
}