POJ1990 MooFest


题意简述

有$n$个牛每个牛有听力$v$和位置$x$,对于每个牛对$(i,j)$能产生$max(v_i,v_j)\cdot |x_i-x_j|$求所有牛对的能量和

题解

首先应该想到是一个统计题,那$max$就有点难处理,不妨给定一个顺序把牛按听力排序,这样一边遍历一边处理
现在假设已经考虑到$i$,前面都是听力比$i$小的,那么距离和如何统计呢?我们可以做一个分类,距离比$i$小的和距离比$i$大的
对于距离比$i$小的,我们求出距离比$i$小的个数$t$,这$t$个牛距离和为$sum_1$,那么对答案就能产生$t\cdot x_i-sum$的贡献,把这个贡献设为$ans_1$
对于距离比$i$大的,我们把目前所有的距离和$sum$减去小于$x$的距离和,那么对答案产生的贡献就是$sum-sum_1-(i-t-1)\cdot x_i$,这两个贡献加起来乘以$v_i$即可
然后每次统计完一个的贡献以后,就把当前距离加进考虑范围,由于两个查询都是查询前缀和,并且是单点修改,所以我们可以用两个树状数组来维护,两个下标都是坐标,一个维护比当前坐标小的牛的个数,另一个维护比当前坐标小的牛的距离的和即可

AC代码

const int maxn=20050;
const int N=20000;
ll n,c1[maxn],c2[maxn];
struct node{
    ll v,x;
    bool operator<(const node&t) const{
        return v<t.v;
    }
}a[maxn];
int lowbit(int x){return x&-x;}
void add1(int x,int p)
{
    while(x<=N)
    {
        c1[x]+=p;
        x+=lowbit(x);
    }
}
void add2(int x,int p)
{
    while(x<=N)
    {
        c2[x]+=p;
        x+=lowbit(x);
    }
}
ll query1(int x)
{
    ll res=0;
    while(x)
    {
        res+=c1[x];
        x-=lowbit(x);
    }
    return res;
}
ll query2(int x)
{
    ll res=0;
    while(x)
    {
        res+=c2[x];
        x-=lowbit(x);
    }
    return res;
}
int main()
{
    cin>>n;
    memset(c1,0,sizeof(c1));
    memset(c2,0,sizeof(c2));
    for(int i=1;i<=n;i++) read(a[i].v),read(a[i].x);
    sort(a+1,a+n+1);
    ll ans=0,sum=0;
    for(int i=1;i<=n;i++)
    {
        ll t=query1(a[i].x);
        ans+=(a[i].x*t-query2(a[i].x))*a[i].v;
        ans+=(sum-query2(a[i].x)-(i-t-1)*a[i].x)*a[i].v;
        sum+=a[i].x;
        add1(a[i].x,1);
        add2(a[i].x,a[i].x);
    }
    cout<<ans<<endl;
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
  目录