题意就是有N头牛，每头牛都有一个坐标和声调值（x, v），两头牛之间通讯要花费的能量是他们的距离乘以最大的一个音调值，现在要任意两头牛之间都相互通讯一次，求总共需要花费多少能量？
显然总共有n*(n+1)/2条，我们可以用树状数组保存，树状数组很适合求区间的和，我们只需要求出某头牛左右两边分别有多少头牛比它的音调小，且他们的坐标和，这样我们就能求出这头牛到其他牛之间的距离和了，因为它的音调值已知且在这先中最大，然后这要求出一头牛与其他比他小的通讯花费的能量了，然后以此求出其他的。这样计算出了它小的，遍历一遍后必然每头牛之间都有里通讯。
#include<iostream>
#include<algorithm>
#define lowbit(x) (x&(-x))
using namespace std;
const int MAX = 20005;
struct data{
int x, w;
}cow[MAX];
int arNum[MAX], arDis[MAX];
bool cmp(data a, data b){
return a.x < b.x;
}
void add(int i, int *ar, int w){
while(i <= MAX-1){
ar[i] += w;
i += lowbit(i);
}
}
__int64 sum(int i, int *ar){
__int64 ans = 0;
while(i > 0){
ans += ar[i];
i -= lowbit(i);
}
return ans;
}
int main(){
int n, i;
__int64 preNum, preDis;
scanf("%d", &n);
for(i = 0; i < n; i ++)
scanf("%d%d", &cow[i].w, &cow[i].x);
sort(cow, cow + n, cmp);
__int64 ans = 0;
memset(arNum, 0, sizeof(arNum)); // 求向左的总能量。
memset(arDis, 0, sizeof(arDis));
for(i = 0; i < n; i ++){
preNum = sum(cow[i].w-1, arNum);
preDis = sum(cow[i].w-1, arDis);
ans += (preNum * cow[i].x - preDis) * cow[i].w;
add(cow[i].w, arNum, 1);
add(cow[i].w, arDis, cow[i].x);
}
memset(arNum, 0, sizeof(arNum)); // 求向右的总能量。
memset(arDis, 0, sizeof(arDis));
for(i = n-1; i >= 0; i --){
preNum = sum(cow[i].w, arNum); // 这里不要用w-1，考虑了声调相等的情况。
preDis = sum(cow[i].w, arDis);
ans += (preDis - preNum * cow[i].x) * cow[i].w;
add(cow[i].w, arNum, 1);
add(cow[i].w, arDis, cow[i].x);
}
printf("%I64d\n", ans);
return 0;
}
