思路
给出一种不需要脑子的四颗树状数组解法。
这四颗树状数组分别为：一颗维护负数，一颗维护负数个数，一颗维护正数，一颗维护正数个数。
首先考虑没有速度该怎么求。
不妨先按 \(x_i\) 从小到大排序，答案为 \(\sum x_i \times (i-1)-sum_i\)，其中 \(sum_i\) 表示 \(\sum_{j=1}^i x_j\)。所以我们不妨先把 \(ans\) 赋值为这个值。
接下来考虑加入速度。
我们只需考虑两种情况：相遇和相离，由于时间无限，所以相遇的情况 \(d_{i,j}\) 一定是 \(0\)，而相离后的距离一定大于 \(0\) 时刻的距离，所以 \(d_{i,j}\) 实际只有两种情况：\(0\)，\(|x_i-x_j|\)。
我们已经把所有的 \(|x_i-x_j|\) 累加入答案，接下来只需要消去 \(0\) 的贡献即可。
设当前扫到的位置为 \(i\)：
- 若 \(v_i>0\)，则此时能与 \(i\) 距离为 \(0\) 的点 \(j\) 必定满足 \(v_j>v_i\)，这是简单的追及问题。
- 若 \(v_i<0\)，则此时能与 \(i\) 距离为 \(0\) 的点 \(j\) 必定满足 \(v_j>0\) 或 \(v_j<v_i\)，\(v_j>0\) 是相遇问题，\(v_j<v_i\) 是追及问题。
接下来就可以简单地二维数点了，或者也可以像我一样暴力开四颗树状数组维护。
代码
//A tree without skin will surely die.
//A man without face is invincible.
#include<bits/stdc++.h>
using namespace std;
#define int long long
int const N=2e5+10;
int n,b[N],sum[N],hsum[N];
struct node{int x,v;}a[N];
struct Tree_Array{
int c[N];
#define lowbit(x) (x&-x)
inline void update(int x,int v){while (x<=n) c[x]+=v,x+=lowbit(x);}
inline int query(int x){int res=0;while (x) res+=c[x],x-=lowbit(x);return res;}
}T[5];
inline bool cmp(node a,node b){return a.x<b.x;}
signed main(){
//读入
sort(b+1,b+n+1);int l=unique(b+1,b+n+1)-b-1;//离散化
for (int i=1;i<=n;++i) a[i].v=lower_bound(b+1,b+l+1,a[i].v)-b;
sort(a+1,a+n+1,cmp);int ans=0;
for (int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i].x;
for (int i=n;i>=1;--i) hsum[i]=hsum[i+1]+a[i].x;
for (int i=1;i<=n;++i) ans+=a[i].x*(i-1)-sum[i-1];
int sum0=0,sum=0;
for (int i=1;i<=n;i=i){
int j=i;while (a[j+1].x==a[i].x) ++j;
for (int k=i;k<=j;++k){
if (!b[a[k].v]){
ans-=a[k].x*T[3].query(n)-T[0].query(n);
continue;
}
if (b[a[k].v]>0) ans-=a[k].x*(T[3].query(n)-T[3].query(a[k].v))-(T[0].query(n)-T[0].query(a[k].v));
else ans-=a[k].x*sum0-sum+a[k].x*(T[3].query(n)+(T[4].query(n)-T[4].query(a[k].v)))-(T[0].query(n)+(T[1].query(n)-T[1].query(a[k].v)));
}
for (int k=i;k<=j;++k){
if (!b[a[k].v]){
++sum0;
sum+=a[k].x;
continue;
}
if (b[a[k].v]>0) T[0].update(a[k].v,a[k].x),T[3].update(a[k].v,1);
else T[1].update(a[k].v,a[k].x),T[4].update(a[k].v,1);
}
i=j+1;
}
//输出
return 0;
}