洛谷 P2345 奶牛集会解题报告

P2345 奶牛集会

题目背景

MooFest, 2004 Open

题目描述

约翰的N 头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很

多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i 头奶牛的坐标为Xi，没有两头奶牛的坐标是相同的。奶牛们的叫声很大，第i 头和第j 头奶牛交流，会发出max{Vi; Vj}×|Xi − Xj | 的音量，其中Vi 和Vj 分别是第i 头和第j 头奶牛的听力。假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。

输入输出格式

输入格式：

• 第一行：单个整数N，1 ≤ N ≤ 20000

• 第二行到第N + 1 行：第i + 1 行有两个整数Vi 和Xi，1 ≤ Vi ≤ 20000; 1 ≤ Xi ≤ 20000

输出格式：

• 单个整数：表示所有奶牛产生的音量之和

对于这个题，要求的即为 (sum_{i=1}^n V_i*sum_{V_j<V_i} |x_i-x_j|)

对于音量(V)，我们可以排序来做以消除影响。

但对于带绝对值的距离，就不太好处理了。

我们考虑去掉绝对值。
(sum_{i=1}^n V_i*(sum_{V_j<V_i,x_i>x_j} (x_i-x_j)*sum_{V_j<V_i,x_i<x_j} (x_j-x_i)))
(Rightarrow sum_{i=1}^n( V_i*(sum_{ V_j<V_i,x_i<x_j }x_j )-V_i*(sum_{ V_j<V_i,x_i>x_j }x_j )+x_i*(k_1-k_2) ))(其中，(k_1)存储位置在(x_i)左边的点的个数，(k_2)右边)

我们使用两个树状数组(c1)和(c2)分别维护(1)~(n)的坐标之和，和(1)~(n)的点的个数。其中(1)~(n)表示按位置离散化的值。

我们将(v)从小到大排序并将这个点加入树状数组即可。

code:

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const ll N=20010;
ll c1[N],c2[N];//奶牛个数，奶牛距离和
ll n;
struct node
{
    ll x,v,i;
    bool friend operator <(node n1,node n2)
    {
        return n1.x<n2.x;
    }
}cow[N],d[N];
bool cmp(node n1,node n2)
{
    return n1.v<n2.v;
}

void change(ll i,ll delta)
{
    while(i<=n)
    {
        c1[i]++;
        c2[i]+=delta;
        i+=i&-i;
    }
}

ll x_query(ll i)
{
    ll x=0;
    while(i)
    {
        x+=c2[i];
        i-=i&-i;
    }
    return x;
}

ll c_query(ll i)
{
    ll c=0;
    while(i)
    {
        c+=c1[i];
        i-=i&-i;
    }
    return c;
}
ll ans=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&cow[i].v,&cow[i].x);
    sort(cow+1,cow+1+n);
    for(int i=1;i<=n;i++)
        cow[i].i=i;
    for(int i=1;i<=n;i++)
    {
        d[cow[i].i].i=i;
        d[cow[i].i].v=cow[i].v;
        d[cow[i].i].x=cow[i].x;
    }
    sort(d+1,d+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        ans+=d[i].v*(x_query(n)-2*x_query(d[i].i)+(2*c_query(d[i].i)-c_query(n))*d[i].x);
        change(d[i].i,d[i].x);
    }
    printf("%lld
",ans);
    return 0;
}

2018.6.2