MooFest

• 前言(划重点)

  1.题目要求n*(n-1)/2对，即不能重复
  2.答案是 max(v[i],v[j]) × dis(i,j) 的求和

• 解决方案

  1. 既然不能n方，那我们只好单独算出每头牛对于答案的贡献。所以可以按照v从小到大排序，这样可以直接通
     过求出这头牛与之前的牛的总距离求出答案。
  2. 总距离
     
     想一想我们怎么拆这个绝对值,因为我们只按照v的大小排序，没保证下标的有序。这时，我们试着拆一拆,假设有L头奶牛比当前i坐标小，R头比他的坐标大(R=i-1-L),用树状数组每次维护个数，以及坐标之和，求出小于当前下标的距离之和

• 代码

//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")

/*

*/
#include<bits/stdc++.h>

#define R register
#define ll long long
#define inf INT_MAX

using namespace std;

const int N=5e4+10;

int n;
ll s[N],b[N];
//一个维护dis,一个维护个数 
struct nkl
{
    ll v,pos;
}k[N];

inline ll god(nkl xx,nkl yy)
{
    return xx.v<yy.v;
}

inline int lb(int x)
{
    return x&(-x);
}

inline void add(int x)
{
    int res=x;
    for (;x<=5e4;x+=lb(x)) b[x]++,s[x]+=res;
}

inline ll ask(int x)
{
    ll res=0;
    for (;x;x-=lb(x)) res+=b[x];

    return res;
}//个数

inline ll find(int x)
{
    ll res=0;
    for (;x;x-=lb(x)) res+=s[x];

    return res;
}//距离 

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%lld%lld",&k[i].v,&k[i].pos);
    sort(k+1,k+n+1,god);

    ll ans=0,sum=0;
    for (int i=1;i<=n;i++)
    {
        ll lk=ask(k[i].pos),rk=i-1-lk;
        //小的个数
        ll le=find(k[i].pos),re=sum-le;sum+=k[i].pos;

        add(k[i].pos);

        ans+=k[i].v*(lk*k[i].pos-le+re-rk*k[i].pos);
    }

    printf("%lld\n",ans);

    return 0;
}