题目链接：http://poj.org/problem?id=1990
/**//*
题意：
约翰农夫有N(N <= 20000)头牛，每头牛有一个权值Vi，他将它们排成一排，
牛i和牛j的阈值是 两者的距离差*max(Vi, Vj)，现在给出每头牛的权值和它的
位置，求所有两头牛之间的阈值之和。
题解：
树状数组
思路：
我们准备两个树状数组，以每头牛的位置作为树状数组的下标，其中一个用
来表示当前位置的牛的位置的值，另一个则记录当前位置牛的个数，然后对所有
牛以Vi为关键字进行递增排序。
接下来对每头牛进行一次线扫，首先统计比当前这头牛的位置小的和大的牛
的数目和位置和，然后做差求出以当前牛的权值为最大值的阈值总和。之后将这
头牛的数量和位置插入到树状数组中进行更新。
*/
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 20010
#define ll __int64
struct point 
{
int V;
int pos;
}pt[maxn];
ll c[2][maxn];
int n, Max;
ll ABS(ll v) {
return v < 0 ? -v : v;
}
int cmp(point a, point b) {
return a.V < b.V;
}
int lowbit(int x) {
return x & (-x);
}
void add(int idx, int pos, int v) {
while(pos <= Max) {
c[idx][pos] += v;
pos += lowbit(pos);
}
}
ll sum(int idx, int pos) {
ll s = 0;
while(pos > 0) {
s += c[idx][pos];
pos -= lowbit(pos);
}
return s;
}
int main() {
int i;
while(scanf("%d", &n) != EOF) {
Max = 0;
for(i = 0; i < n; i++) {
scanf("%d %d", &pt[i].V, &pt[i].pos);
if(pt[i].pos > Max)
Max = pt[i].pos;
}
for(i = 1; i <= Max; i++)
c[0][i] = c[1][i] = 0;
sort(pt, pt + n, cmp);
ll ans = 0;
for(i = 0; i < n; i++) {
ans += ABS((sum(0, Max) - sum(0, pt[i].pos)
- (sum(1, Max) - sum(1, pt[i].pos)) * pt[i].pos)) * pt[i].V;
ans += ABS((sum(0, pt[i].pos)
- sum(1, pt[i].pos) * pt[i].pos)) * pt[i].V;
add(0, pt[i].pos, pt[i].pos);
add(1, pt[i].pos, 1);
}
printf("%I64d\n", ans);
}
return 0;
}