分析

对于 我们非常不好处理，可以考虑 分治。先按 由小到大排序。那么所有右侧的 一定大于左侧。在处理某一层时，再按 排序。这样处理答案就非常方便了。维护一个前缀和和一个后缀和。两个指针移一下。使用快排的时间复杂度为 ，可以在分治过程中归并排序从此复杂度为 。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
const int inf = 0x3f3f3f3f;
int read(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f ? -x : x ;
}
const int N = 5e4+100;
struct Node{
    int v,x;
}s[N];
int n;
LL ans = 0;
bool cmpx(Node a,Node b) {
    return a.x < b.x; 
}
bool cmpv(Node a,Node b) {
    return a.v < b.v;
}
void cdq(int l,int r) 
{
    if(r - l == 0) return;
    int mid = l + r >> 1;
    cdq(l,mid);cdq(mid+1,r);
    sort(s+l,s+mid+1,cmpx);
    sort(s+mid+1,s+r+1,cmpx);
    LL s1 = 0,s2 = 0;
    for(int i = l;i <= mid;i++) s1 += s[i].x;
    LL pos = l;
    LL n2 = 0,n1 = mid-l+1;
    for(int i = mid+1;i <= r;i++) 
    {
        while(pos <= mid && s[i].x > s[pos].x) {
            s2 += s[pos].x;
            s1 -= s[pos].x;
            pos++;
            n2++;n1--;
        }
        ans += 1LL * s[i].v * (s1 - s[i].x * n1);
        ans += 1LL * s[i].v * (s[i].x * n2 - s2);
    }
}
int main()
{
    n = read();
    for(int i = 1;i <= n;i++) {
        s[i].v = read();s[i].x = read();
    }
    sort(s+1,s+1+n,cmpv);
    cdq(1,n);
    cout << ans << endl;
    return 0;
}