若至题,先套路按 $a$ 排序然后直接树状数组维护前面和后面与 $x$ 之间的距离。
写的有点小长。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 15;
int n;
struct node {
int a, x;
} a[N];
bool cmp(node a, node b) {
return a.a < b.a;
}
int tr1[N], tr2[N];
void add1(int x) {
for ( ; x < N; x += x & -x) tr1[x]++;
}
int query1(int x) {
int res = 0;
for ( ; x ; x -= x & -x) res += tr1[x];
return res;
}
void add2(int x, int id) {
for ( ; x < N; x += x & -x) tr2[x] += id;
}
int query2(int x) {
int res = 0;
for ( ; x ; x -= x & -x) res += tr2[x];
return res;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].a, &a[i].x);
sort(a + 1, a + 1 + n, cmp);
// for (int i = 1; i <= n; i++) cout << a[i].a << ' ' << a[i].x << endl;
long long ans = 0;
for (int i = 1; i <= n; i++) {
int x = a[i].x;
long long lt = query1(x) * 1ll * x - query2(x);
long long rt = (query2(N - 1) - query2(x)) - (query1(N - 1) - query1(x)) * 1ll * x;
ans += a[i].a * (lt + rt);
add1(a[i].x), add2(a[i].x, a[i].x);
}
printf("%lld\n", ans);
return 0;
}