一道有趣的树状数组题

ACM算法日常

发布于 2020-02-16 20:01:22

4790

发布于 2020-02-16 20:01:22

文章被收录于专栏：ACM算法日常

有趣的树状数组题目

Every year, Farmer John's N (1 <= N <= 20,000) cows attend "MooFest",a social gathering of cows from around the world. MooFest involves a variety of events including haybale stacking, fence jumping, pin the tail on the farmer, and of course, mooing. When the cows all stand in line for a particular event, they moo so loudly that the roar is practically deafening. After participating in this event year after year, some of the cows have in fact lost a bit of their hearing.

Each cow i has an associated "hearing" threshold v(i) (in the range 1..20,000). If a cow moos to cow i, she must use a volume of at least v(i) times the distance between the two cows in order to be heard by cow i. If two cows i and j wish to converse, they must speak at a volume level equal to the distance between them times max(v(i),v(j)).

Suppose each of the N cows is standing in a straight line (each cow at some unique x coordinate in the range 1..20,000), and every pair of cows is carrying on a conversation using the smallest possible volume.

Compute the sum of all the volumes produced by all N(N-1)/2 pairs of mooing cows.

Input

* Line 1: A single integer, N

* Lines 2..N+1: Two integers: the volume threshold and x coordinate for a cow. Line 2 represents the first cow; line 3 represents the second cow; and so on. No two cows will stand at the same location.

Output

* Line 1: A single line with a single integer that is the sum of all the volumes of the conversing cows.

Sample Input

Sample Output

题意：给一些牛，每头牛有位置和音量两个变量。两头牛之间通讯的花费为max(ai,aj)*dis。两牛的音量最高值 * 两牛距离，求所有牛之间的交流的花费。

暴力的话就是O(n^2)。题目数据这样子搞肯定超时。那么我们可以想想数据结构来优化。可以想到，我们对每对牛进行处理的时候，我们优先考虑的是音量大的那头牛。那么我们从音量小的牛开始算起。先按音量排个序。

拿第i头牛，计算的时候，我们要考虑到在他前面的比它音量小的牛和在它后面的比它音量小的牛。就有vol(i)*(sumfront+sumlast)。前面的牛的距离总和sumfront为当前牛的位置 * 在前面的牛的个数(音量比当前牛小)减去到当前牛累计的位置之和。sumlast的计算很巧妙，用已经遍历过的前缀和(音量比当前牛小，代码中用total表示)减去当前牛前面的所有牛的位置之和再减去当前位置 * 右边的牛的个数(这里包括它本身)`。

代码中sumfront和sumlast分别用sum1和sum2表示。注意的是结果比较大要用longlong表示。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=20000+100;
struct node
{
	int v,pos;
	bool operator<(const node &a)const {
		return v<a.v;
	}
}no[maxn];
int a[2][maxn];
int n;
void add(int i,int x,int val)
{
	while(x<maxn)
	{
		a[i][x]+=val;
		x+=x&(-x);
	}
}
int sum(int i,int x)
{
	int ans=0;
	while(x>0)
	{
		ans+=a[i][x];
		x-=x&(-x);
	}
	return ans;
}//以上是树状数组模板~
int main()
{
	cin>>n;
	memset(a,0,sizeof a);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&no[i].v,&no[i].pos);
	}
	sort(no,no+n);
	ll ans=0;
	int total=0;
	for(int i=0;i<n;i++)
	{
		int x=no[i].pos;
		total+=x;
		add(0,x,1);
		add(1,x,x);
		int num1=sum(0,x),num2=sum(1,x);//计算frontsum和lastsum
		int t1=num1*x-num2;//计算音量小于当前且位置小于当前的位置总和
		int t2=total-num2-x*(i+1-num1);//计算音量小于当前且位置大于当前的位置总和
		ans+=(long long)(t1+t2)*no[i].v;
	}
	cout<<ans<<endl;
}