1:暴力AC（ ans += (long long)(max(arr[i].v, arr[j].v) * abs(arr[i].x - arr[j].x));）

#include<iostream>
#include<cmath>
using namespace std;
int n;
struct s
{int v, x;
}arr[20005];
long long ans;
int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> arr[i].v >> arr[i].x;for(int i=1;i<n;i++)for (int j = i + 1; j <= n; j++){ans += (long long)(max(arr[i].v, arr[j].v) * abs(arr[i].x - arr[j].x));}cout << ans << endl;return 0;
}

2：分治算法

这题其实可以什么数据结构都不用，分治

将数组先按v值排序

然后找到中点mid，左右递归处理

因为v值排过序，所以右边的v值一定大于左边v值

就剩x不好算了

看到绝对值，最简单的方法就是去绝对值符号

所以我们应该枚举右边mid+1到r的区间，找到有哪些x值比当前小，哪些比它大

右边的v值一定大于左边v值，求和乘a[i].v就行了

但是，这又该怎么做呢？

也许左右x值为升序就好做了，这就像求逆序对一样

因此我们再对序列进行归并排序

尽管这会对v值的升序进行破环，但由于中间的划分，所以左右不会混合，前面那个 性质还能保证

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <algorithm>
using namespace std;
int n,i;
long long ans;
struct str{int x,v;
}a[100005],tmp[100005];
bool cmp(str x,str y)
{return x.v<y.v;
}
void cdqdfs(int l,int r)
{if(l>=r)return;int mid=(l+r)/2,ll=l,i;long long s1=0,s2=0;cdqdfs(l,mid);cdqdfs(mid+1,r);for(i=l;i<=mid;i++)s1+=a[i].x;for(i=mid+1;i<=r;i++){while(ll<=mid&&a[ll].x<a[i].x)//ll为划分的中点，其左边都小于a[i].x，右边都大于或等于a[i].x{s2+=a[ll].x;s1-=a[ll].x;ll++;}ans+=(1ll*a[i].x*(ll-l)-s2-1ll*a[i].x*(mid-ll+1)+s1)*a[i].v;}int l1=l,l2=mid+1,k=l-1;while(l1<=mid||l2<=r)//归并排序{if((a[l1].x>a[l2].x||l1>mid)&&l2<=r){tmp[++k]=a[l2];l2++;}else{tmp[++k]=a[l1];l1++;}}for(i=l;i<=r;i++)a[i]=tmp[i];
}
int main(){scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d %d",&a[i].v,&a[i].x);sort(a+1,a+1+n,cmp);cdqdfs(1,n);cout<<ans;
}

over