poj 1990 MooFest 树状数组

      显然总共有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;
}