PKU 1990 MooFest
英雄哪里出来发表于 2011-04-09 14:06:00
题目链接：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 __int64struct 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;}