题意

每一年，约翰的 $ N $ 只奶牛参加奶牛狂欢节。这是一个全世界奶牛都参加的大联欢。狂欢节包括很多有趣的活动，比如干草堆叠大赛、跳牛栏大赛，奶牛之间有时还相互扎屁股取乐。当然，她们会排成一列嚎叫，来欢庆她们的节日。奶牛们的叫声实在刺耳，以致于每只奶牛的听力都受到不同程度的损伤。现在告诉你奶牛 $ i $ 的听力为 $ v_i $ ，这表示如果奶牛 $ j $ 想说点什么让她听到，必须用高于 $ v_i \times dis(i,j) $ 的音量。因此，如果奶牛 $ i $ 和 $ j $ 想相互交谈，她们的音量必须不小于 $ \max (v_i,v_j) \times dis(i,j) $。其中 $ dis(i,j) $ 表示她们间的距离。

现在 $ N $ 只奶牛都站在一条直线上了，每只奶牛还有一个坐标 $ x_i $。如果每对奶牛都在交谈，并且使用最小音量，那所有 $ N(N-1)/2 $ 对奶牛间谈话的音量之和为多少？

Input

第 $1$ 行输入一个整数 $ N $ 。

接下来 $ N $ 行，每行输入两个数 $ v_i $ 和 $ x_i $ ，分别代表第 $ i $ 头奶牛的听力和坐标。

Output

输出一个数，代表这 $ N(N-1)/2 $ 对奶牛谈话时的音量之和。

Sample Input

4
3 1
2 5
2 6
4 3

Sample Output

57

题解

我们先对所有的牛按音量 $v$ 从小到大进行排序，则当我们处理到第 $i$ 头牛时，我们只和 $i$ 前面的牛比，这些牛的$v$ 一定都比当前牛小，因此 $max(v_i,v_j)$ 的值可以直接取 $v_i$ 。
那么题目要求的$ans = ∑(v_i*(∑|x_i-x_j|)),v_j < v_i$
分情况考虑，$ans=∑(v_i * (x_i * lessnum-∑x_{j1}+∑x_{j2}-x_i * greaternum)$。
$lessnum表示坐标小于x_i的牛的数目，greaternum表示坐标大于x_i的牛的数目$
$∑x_{j1}为坐标小于x_i的牛的坐标之和，∑x_{j2}为坐标大于x_i的牛的坐标之和$

树状数组可以用来快速地求出某个区间内和，利用这个性质，我们可以快速地求出对于牛$i$，$x_i$位置前后比$v_i$小的牛的个数，以及坐标之和。

这里就需要两个树状数组，一个记录比$v_i$小的牛的个数cnt，一个记录比$v_i$小的牛的位置之和距离之和dist。

分别统计比$v_i$且位于$x_i$坐标之前的牛的数目left，比$v_i$且位于$x_i$坐标之后的牛的数目right，
则$ans=∑v_i * ((left * x_i-sum(1,x-1))+(sum(x+1,maxd)-right * x))$,

$sum(1,x-1)和sum(x+1,maxd)$分别表示位于$x_i$之前所有牛的坐标之和，位于$x_i$之后所有牛的坐标之和。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
#define fi first
#define se second
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef pair<int,int> PII;
typedef pair<double,double> pdd;
typedef pair<double,int> pdi;
typedef long long LL;
const int INF=0x3f3f3f3f;
const LL IINF=0x3f3f3f3f3f3f3f3f;

const int N=20010;
PII cow[N];
LL cnt[N];
LL dist[N];
int n;
int maxd;

int lowbit(int x)
{
    return x&-x;
}

void add(LL *tr,int x,int d)
{
    for(int i=x;i<=maxd;i+=lowbit(i))
        tr[i]+=d;
}

LL sum(LL *tr,int x)
{
    LL res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=tr[i];
    return res;
}

LL sum(LL *tr,int l,int r)
{
    return sum(tr,r)-sum(tr,l-1);
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>cow[i].first>>cow[i].second,maxd=max(maxd,cow[i].second);
    sort(cow,cow+n);

    LL res=0;
    for(int i=0;i<n;i++)
    {
        int v=cow[i].first,x=cow[i].second;
        LL left=sum(cnt,1,x-1),right=sum(cnt,x+1,maxd);
        res+=v*((left*x-sum(dist,1,x-1))+(sum(dist,x+1,maxd)-right*x));
        add(cnt,x,1);
        add(dist,x,x);
    }

    cout<<res<<endl;

   // system("pause");
}