Luogu P2345 奶牛集会

解析

• 先按照奶牛的听力从小到大排序，这样可以保证我们处理第 i 头奶牛时，已经处理过的奶牛都用这头奶牛的听力作为音量基础值
• 然后用两个树状数组分别维护数量和坐标之和，然后处理答案即可，具体看代码

Code

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N=20005;
struct cow
{
    int v,x;
}c[N];
int n;
LL ans,ctr[2][N];
bool cmp(cow a,cow b)
{
    if(a.v==b.v) return a.x<b.x;
    else return a.v<b.v;
}
int lowbit(int u)
{
    return u&(-u);
}
void update(int u,int w,int id)
{
    for(;u<=20000;u+=lowbit(u)) ctr[id][u]+=w;
    return;
}
LL query(int u,int id)
{
    LL res=0;
    for(;u;u-=lowbit(u)) res+=ctr[id][u];
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&c[i].v,&c[i].x);
    sort(c+1,c+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        update(c[i].x,1,0);
        update(c[i].x,c[i].x,1);
        LL bef=query(c[i].x,0)*c[i].x-query(c[i].x,1);
        LL beh=query(20000,1)-query(c[i].x,1)-(i-query(c[i].x,0))*c[i].x;
        ans+=c[i].v*(bef+beh);
    }
    printf("%lld\n",ans);
    return 0;
}