题意

$n$ 个元素，每个元素分别有两个权值 $a_i,b_i$ ，求 $\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\max(a_i,a_j)\times |b_i-b_j|$ 。

思路

还是分治。考虑到这里头可以搞出单调性以及归并来搞点事情。由于我们这里需要 $\max$ ，所以我们最一开始可以通过对 $a_i$ 来排序，保证在归并的时候，右半区间的 $a$ 一定不小于左半区间。

接下来在指针挪动的时候，主要看 $b$ 的情况。很显然，就是找到小于等于 $b_i$ 的边界，然后根据绝对值的公式计算 $\max a_i~(i\in[m+1,r])$ 乘积的和是多少就行了。归并的时候按照 $b$ 从小到大归并，就能保证每个递归层用一个单调指针跑就行了。

代码

struct info
{
    i64 a, b;
    info& operator=(const info& o) { return a = o.a, b = o.b, (*this); }
};
int n;
info a[N], b[N];
i64 ans;
bool cmpa(const info& x, const info& y) { return (x.a ^ y.a) ? (x.a < y.a) : (x.b < y.b); }
bool cmpb(const info& x, const info& y) { return (x.b ^ y.b) ? (x.b < y.b) : (x.a < y.a); }

void solve(int l, int r)
{
    if (!(l ^ r))
        return;
    int m = (l + r) >> 1;
    solve(l, m), solve(m + 1, r);
    i64 gt_b = 0, le_b = 0;
    for (int i = l; i <= m; ++i)
        gt_b += a[i].b;
    for (int i = m + 1, j = l; i <= r; ++i)
    {
        while (j <= m && a[j].b <= a[i].b)
            gt_b -= a[j].b, le_b += a[j].b, ++j;
        ans += a[i].a * ((gt_b - a[i].b * (m - j + 1)) + (a[i].b * (j - l) - le_b));
    }
    std::merge(a + l, a + m + 1, a + m + 1, a + r + 1, b + l, cmpb);
    for (int i = l; i <= r; ++i)
        a[i] = b[i];
}

int main()
{
    n = rd();
    for (int i = 1; i <= n; ++i)
        a[i].a = rd(), a[i].b = rd();
    std::sort(a + 1, a + n + 1, cmpa);
    solve(1, n);
    wr(ans);
}