本质上是一道统计点对之间贡献的题目。
将每个奶牛看作一个点对\((v_i,x_i)\)，\(i\)能对\(j\)产生贡献，当且仅当下面条件其一成立：
- \(v_i\le v_j,x_i>x_j\)，此时的贡献为\((x_i-x_j)\times v_j\)。
- \(v_i\le v_j,x_i<x_j\)，此时的贡献为\((x_j-x_i)\times v_j\)。
大体思路是这样，有不同的实现方法。
Sol #1 树状数组
根据上面的分析，我们可以将点对按\(v\)从小到大排序，依次遍历，将\(x\)丢进树状数组。
\(i\)之前的\(x\)被丢进树状数组后，统计对\(i\)的贡献。
- 先查树状数组中\(x\in [1,x_i-1]\)的\(x\)之和，记为\(s\)，这样的\(x\)的个数记为\(c\)，对答案的贡献即为\((c\times x_i-s)\times v_i\)；
- 再查\([x_i+1,+\infty]\)，对答案的贡献为\((s-c\times x)\times v_i\)。
时间复杂度\(O(n\log V)\)，其中\(V\)是值域。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+10,Ve=5e4,V=Ve+10;//e=exact
int n,ans;
inline int lb(int x){return x&-x;}
struct BIT{int s[V],c[V];void chp(int x,int v){for(;x<=Ve;x+=lb(x)) s[x]+=v,c[x]++;}void qry(int x,int y,int& _s,int& _c){_s=_c=0,x--;for(;y;y-=lb(y)) _s+=s[y],_c+=c[y];for(;x;x-=lb(x)) _s-=s[x],_c-=c[x];}
}bit;
struct Node{int a,v;}a[N];
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i].v>>a[i].a;sort(a+1,a+1+n,[](Node a,Node b){return a.v<b.v;});for(int i=1,s,c;i<=n;i++){bit.qry(1,a[i].a-1,s,c);ans+=a[i].v*(c*a[i].a-s);bit.qry(a[i].a+1,Ve,s,c);ans+=a[i].v*(s-c*a[i].a);bit.chp(a[i].a,a[i].a);}cout<<ans<<"\n";return 0;
}
Sol #2 CDQ分治
统计点对贡献，当然少不了CDQ分治～
不妨对\(v\)分治，按照\(x\)合并。
具体来说，将\(v\)从小到大排序，然后从\([1,n]\)开始不断分成左右两个区间递归处理，每个子问题只计算跨区间的贡献。这也是CDQ分治的核心思想。
递归处理完左右子问题后，将左右区间内部按\(x\)从小到大排序，尽管\(v\)的顺序已经被打乱，但是由于是区间内部的排序，所以左区间的\(v\)值始终\(\le\)右区间的\(v\)值。仅需关心\(x\)之间的关系。
我们用双指针\(i,j\)分别指向左右区间，\(j\)每次移动之前，\(i\)都移动到最大的位置使得\(x_i<x_j\)。这样\([l,i]\)的点对满足第二个条件，\([i+1,mid]\)的点对满足第一个条件。对照式子统计即可。
按\(x\)排序的过程如果写成sort会是\(O(n\log^2 n)\)的，可以在递归的同时进行归并排序，这样就可以降到\(O(n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+10;
int n,ans;
struct Node{int a,v;}a[N],t[N];
int cdq(int l,int r){//返回值为[l,r]内a的和if(l==r) return a[l].a;int mid=(l+r)>>1,i,j,k,s=0,sl=cdq(l,mid),sr=cdq(mid+1,r);for(i=k=l,j=mid+1;j<=r;j++){while(i<=mid&&a[i].a<a[j].a) s+=a[i].a,t[k++]=a[i++];ans+=a[j].v*(((i-l)*a[j].a-s)+((sl-s)-(mid+1-i)*a[j].a));t[k++]=a[j];}while(i<=mid) t[k++]=a[i++];for(i=l;i<=r;i++) a[i]=t[i];return sl+sr;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i].v>>a[i].a;sort(a+1,a+1+n,[](Node a,Node b){return a.v<b.v;});cdq(1,n);cout<<ans<<"\n";return 0;
}