POJ 1990 MooFest

問題

1990 -- MooFest

解法

まず考え方ですが, v(i) が小さい順に牛を並べていく, というふうに考えた場合, i 番目の牛の volume threshold が v(i) 以下の牛と対をなしてつくられるコストは,

v(i) * (それぞれの牛との距離)

というようになります。また, それぞれの牛との距離というのは, i 番目の牛より左側にいる牛の数を lnum, 右側にいる牛の数を rnum, i 番目の牛より左側にいる牛の座標値の合計を lsum, 左側にいる牛の座標値の合計を rsum とすると,

(lnum * xi - lsum) + (rnum * xi - rsum)

というように簡単に計算が出来ます。ということで, 各座標値 x について, 「x より左側にいる牛の数」および「x より左側にいる牛の座標値の合計」を求める BIT を用意しておけば, で答えを求めることが出来ます。

const int MAXN = 20020;
pair<ll, ll> P[MAXN];
int N;

struct BIT {
    int n;
    vector<ll> bit;
    BIT(int n) : n(n), bit(n+1, 0) {}
    ll sum(int i) {
        ll ret = 0;
        while (i) {
            ret += bit[i];
            i -= i&-i;
        }
        return ret;
    }
    void add(int i, ll x) {
        while (i <= n) {
            bit[i] += x;
            i += i&-i;
        }
    }
};

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%lld %lld", &P[i].first, &P[i].second);
    sort(P, P+N);
    ll ans = 0;
    // b1: i の左側にいる牛の数
    // b2: 座標 i より左側にいる牛の座標値の合計
    BIT b1(MAXN), b2(MAXN);
    for (int i = 0; i < N; i++) {
        pair<ll, ll> p = P[i];
        ll lnum = b1.sum((int)p.second);
        ll rnum = i-lnum;
        ll lsum = b2.sum((int)p.second);
        ll rsum = b2.sum(MAXN)-b2.sum((int)p.second);
        ans += p.first * (lnum*p.second - lsum);
        ans += p.first * (rsum-rnum*p.second);
        b1.add((int)p.second, 1);
        b2.add((int)p.second, p.second);
    }
    cout << ans << endl;
    return 0;
}