P5094 [USACO04OPEN] MooFest G 加强版
tags：【普及+/提高】 【树状数组】【cdq 分治】
题目让求：
\[\sum_{1 \le j < i \le n} \max(v_i,v_j) \times |x_i - x_j|
\]
对 \(v\) 排序，即：
\[\sum_{1 \le j < i \le n} v_i \times |x_i - x_j|
\]
考虑处理绝对值，把绝对值拆开：
\[\sum_{1 \le j < i \le n} v_i \times (x_i - x_j) = \sum_{1 \le j < i \le n} v_i \times x_i - v_i \times x_j = \sum_{1 \le i \le n} v_i \times x_i - \sum_{1 \le j < i \le n} v_i \times x_j \times [x_j < x_i]
\]
绝对值内是负数的拆分同理，上面是非负数的拆分。
因此，我们只需要维护两个树状数组（BIT），分别维护前 \(i\) 个中 \(x_j\) 不超过 \(x_i\) 的个数，以及 \(x_j\) 不超过 \(x_i\) 的权值和即可。
时间复杂度 \(O(n \log n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 50005;
const int V = 50000;
int n,cnt[N];
long long tot,ans,sum[N];
struct node
{int v,x;
}a[N];
void insert(int x,int d)
{while (x <= V){cnt[x]++;sum[x] += d;x += (x & (-x));}
}
int query_cnt(int x)
{int res = 0;while (x){res += cnt[x];x -= (x & (-x));}return res;
}
long long query_sum(int x)
{long long res = 0;while (x){res += sum[x];x -= (x & (-x));}return res;
}
bool cmp(node a,node b)
{return a.v < b.v;
}
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&a[i].v);scanf("%d",&a[i].x);}sort(a+1,a+n+1,cmp);for (int i=1;i<=n;i++){insert(a[i].x,a[i].x), tot += a[i].x;int num = query_cnt(a[i].x);ans += 1ll * a[i].v * (1ll * a[i].x * num - query_sum(a[i].x));ans += 1ll * a[i].v * ((tot - query_sum(a[i].x)) - 1ll * a[i].x * (i-num));}printf("%lld",ans);return 0;
}