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