题意就是有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; }
