POJ 1990 - MooFest

题目描述

MooFest

解法：多重树状数组（C++）

我们先来翻译题目，每头牛有两个值 $v$ 和 $x$，两头牛对话所要的能量是 $max(v_i,v_j)?abs(x_i?x_j)$

要求的是所有牛对话所需要的能量，即

$$\sum _i^n\sum _{j?=i}max(v_i,v_j)?abs(x_i?x_j)$$

现在明白题意了吧

接着我们说做法，

先按照 $v$ 从小到大排列一下，这样上面的式子就可以简化为

$$\sum _{i>j}{v}_i?abs(x_i?x_j)=v_i?\sum _{i>j}abs(x_i?x_j)$$

那么，接下来的事情就是求距离和，我们将距离划分为两部分：$x$ 小于 $x_i$的部分和 $x$ 大于 $x_i$的部分，放到数轴上连看就是在 $i$ 左边的和在 $i$ 右边的。

对于左边的距离和，我们有 $x_i?cnt?dis$，其中 $cnt$ 表示左边部分的牛的个数，$dis$ 表示左边部分牛的 $x$ 的和。

为什么这个公式有效呢？

接着我们看右边部分，$all?dis$ 剩下的是就是右边部分的牛的 $x$ 的和，右边部分的牛的个数等于$i?cnt?1$，于是，最终的计算公式即 $all?dis?(i?cnt?1)?x_i$

通过上面分析，看得出来，我们需要用到两个树状数组，一个用于记录 $x$，一个用于记录对应 $x$ 的个数

#include <iostream>
#include <algorithm>using namespace std;typedef long long ll;const ll N = 1e5;
ll c[2][N];
ll n, cnt, dis, lleft, rright, all=0, ans=0;struct Cow{
    int v, x;
}cows[N];bool cmp(const Cow& a, const Cow& b){
    return a.v<b.v;}ll lowbit(ll x){
    return x&(-x);}void add(ll x, int op){
    for(ll i=x;i<=N;i+=lowbit(i))c[op][i] += op?x:1;
}ll sum(ll x, int op){
    ll s = 0;for(ll i=x;i;i-=lowbit(i))s += c[op][i];return s;
}int main()
{
    cin >> n;for(int i=1;i<=n;i++)cin >> cows[i].v >> cows[i].x;sort(cows+1, cows+1+n, cmp);for(int i=1;i<=n;i++){
    cnt = sum(cows[i].x, 0);dis = sum(cows[i].x, 1);lleft = cnt*cows[i].x-dis;rright = all-dis-(i-cnt-1)*cows[i].x;cout << cows[i].v << " " << cnt << " " << dis << " " << lleft << " " << right << endl;ans += (lleft+rright)*cows[i].v;all += cows[i].x;add(cows[i].x, 0);add(cows[i].x, 1);}cout << ans << endl;return 0;
}