題目鏈接：http://poj.org/problem?id=1990
/**//*
題意：
約翰農(nóng)夫有N(N <= 20000)頭牛，每頭牛有一個權(quán)值Vi，他將它們排成一排，
牛i和牛j的閾值是 兩者的距離差*max(Vi, Vj)，現(xiàn)在給出每頭牛的權(quán)值和它的
位置，求所有兩頭牛之間的閾值之和。
題解：
樹狀數(shù)組
思路：
我們準備兩個樹狀數(shù)組，以每頭牛的位置作為樹狀數(shù)組的下標，其中一個用
來表示當(dāng)前位置的牛的位置的值，另一個則記錄當(dāng)前位置牛的個數(shù)，然后對所有
牛以Vi為關(guān)鍵字進行遞增排序。
接下來對每頭牛進行一次線掃，首先統(tǒng)計比當(dāng)前這頭牛的位置小的和大的牛
的數(shù)目和位置和，然后做差求出以當(dāng)前牛的權(quán)值為最大值的閾值總和。之后將這
頭牛的數(shù)量和位置插入到樹狀數(shù)組中進行更新。
*/
#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;
}