本题有两种做法，做法一，基于树状数组优化，做法二，分治法
这里讲一下分治做法(类似归并排序)：
按 作为第一关键字排序, for j=mid+1 to r 枚举的贡献和
由归并排序特点，和两个区间内已经按照第二关键字排好序。寻找和x>x_jx<x_jx_i$。贡献和为
前缀和预处理，查询复杂度$O(1)。
贡献加完后，对第二关键字归并排序。
参考代码如下：
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
int x, v;
} a[50005];
bool cmp(node aa, node bb) {
return aa.v < bb.v; //按v从小到大排序
}
int ans = 0, sum[50005];
void merge(int l, int r) {
int mid = (l + r) / 2;
sum[l - 1] = 0;
for (int i = l; i <= r; i++) {
sum[i] = sum[i - 1] + a[i].x;
}
for (int j = mid + 1; j <= r; j++) {
int ii = l - 1; // i:寻找x<xj的所有x，i标志分界线（最后一个满足的）:由于归并排序，已经按x从小到大排序
while (ii < mid && a[ii + 1].x < a[j].x) {
ii++;
}
ans += a[j].v *
((ii - l + 1) * a[j].x - (sum[ii] - sum[l - 1]) + (sum[mid] - sum[ii]) - (mid - ii) * a[j].x);
}
//中间跨越部分处理完成后，即可对合并的整体按第二关键字x排序，不影响后续结果。
node aux[r - l + 1];
for (int i = l; i <= r; i++) {
aux[i - l] = a[i];
}
int i1 = l, i2 = mid + 1;
for (int i = l; i <= r; i++) {
if (i1 > mid) {
a[i] = aux[i2 - l];
i2++;
} else if (i2 > r) {
a[i] = aux[i1 - l];
i1++;
} else if (aux[i1 - l].x >= aux[i2 - l].x) {
a[i] = aux[i2 - l];
i2++;
} else {
a[i] = aux[i1 - l];
i1++;
}
}
}
void mergesort(int l, int r) {
if (l >= r)
return;
int mid = (l + r) / 2;
mergesort(l, mid);
mergesort(mid + 1, r);
merge(l, r);
}
signed main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].v >> a[i].x;
}
sort(a, a + n, cmp);
mergesort(0, n - 1);
cout << ans;
}