题目
约翰的N 头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很
多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i 头奶牛的坐标为Xi，没有两头奶牛的坐标是相同的。奶牛们的叫声很大，第i 头和第j 头奶牛交流，会发出max{Vi; Vj}×|Xi − Xj | 的音量，其中Vi 和Vj 分别是第i 头和第j 头奶牛的听力。假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。
输入格式：
• 第一行：单个整数N，1 ≤ N ≤ 20000
• 第二行到第N + 1 行：第i + 1 行有两个整数Vi 和Xi，1 ≤ Vi ≤ 20000; 1 ≤ Xi ≤ 20000
输出格式：
• 单个整数：表示所有奶牛产生的音量之和
分析
因为每一次的v取的是两个牛之间的最大值，所以我们先按牛的v从小到大排序，这样我们便无需考虑取最大值的问题，每一次只找在这只牛之前加入树状数组中的牛即可。然后我们在考虑如何计算每只牛所造成的影响，因为需要的是两个牛之间的距离即x的绝对值，所以我们每一次将每一只牛添加到树状数组中这只牛的坐标x的位置，我们用树状数组c1记录某个位置之前所有点的坐标和，c2记录某个位置之前有多少个点。我们将每一次查询分成两半：在这个点之前的和在这个点之后的，这样我们便无限考虑绝对值的问题，前半段为(之前的点的数量)*x-(之前点的坐标和)，后半段为(之后点的坐标和)-(之后点的数量)*x，前半段的一切信息是最朴素的树状数组查询，而后半段的信息即为整段信息-前半段信息。
代码
#include<bits/stdc++.h>
using namespace std;
struct node{
long long v,x;
}a[110000];
long long c1[110000],c2[110000],n,ans,m;
long long lb(long long x){return x&(-x);}
bool cmp(const node &q,const node &p){
return q.v<p.v;
}
long long w(long long x){
long long t=0;
while(x){
t+=c1[x];
x-=lb(x);
}
return t;
}
long long s(long long x){
long long t=0;
while(x){
t+=c2[x];
x-=lb(x);
}
return t;
}
void add(long long x,long long s,long long t){
while(x<=m){
c1[x]+=s;
c2[x]+=t;
x+=lb(x);
}
}
long long q(long long x,long long v){
return v*(s(x)*x-w(x));
}
long long q2(long long x,long long y,long long v){
return v*(w(y)-w(x)-x*(s(y)-s(x)));
}
int main()
{ long long i,j,k;
scanf("%lld",&n);
for(i=1;i<=n;i++){
scanf("%lld%lld",&a[i].v,&a[i].x);
m=max(m,a[i].x);
}
sort(a+1,a+n+1,cmp);
for(i=1;i<=n;i++){
ans+=q(a[i].x,a[i].v)+q2(a[i].x,m,a[i].v);
add(a[i].x,a[i].x,1);
}
printf("%lld
",ans);
return 0;
}