[USACO]奶牛集会MooFest

发表于 | 阅读次数：

Description

约翰家的N头奶牛每年都会参加“哞哞大会” 。哞哞大会是世界奶牛界的盛事。集会上 的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。当然，哞哞大叫肯定也包括在内。 奶牛们的叫声很大，很多奶牛在参加多年活动之后，实际上已经失去了一部分的听力。

奶牛们已经站在了一条直线上，i号奶牛的坐标为Xi，她只能听到大于Vi的声音。每头奶 牛的位置坐标都是唯一的。

如果i号和j号奶牛想对话，则他们使用的音量为max {Vi, Vj} × |Xi −Xj|。

N头奶牛可以组合成N(N − 1)/2对奶牛，假设每对奶牛都使用最小的音量在对话，请计 算所有奶牛产生的总音量是多少。

Input Format

第一行：单个整数：$N,1 \le N \le 20000$

第二行到第$N + 1$行：每行有两个用空格分开的整数，$Vi$和$Xi$，$1 \le Vi \le 20000， 1 \le Xi \le 20000$

Output Format

第一行：单个整数，表示最小音量之和

Sample Input

1
2
3
4
5
4 
3 1 
2 5 
2 6 
4 3

Sample Output

1
57

题解

扯淡ing……

有人说我博客都荒了（手动@mnihyc）

马上就NOIP2018了，我都没时间写一些东西啊。。。

然后现在写一篇题解算是给自己加个油emmm（我知道很水啦，但是我也没做什么好题…）

正题：

我们考虑式子$max(Vi,Vj) \times |Xi-Xj|$，很明显音量越高的对答案的贡献越大。

所以，我们可以考虑按照音量大小升序排序。那么我们怎么计算$|Xi-Xj|$呢？

我们考虑用树状数组来维护一下在第$i$头牛前，$X$值比第$i$头牛小的个数。

那么这头牛$i$对于答案的贡献就为$(cnt \times Xi-len) \times Vi$

其中$cnt$为在第$i$头牛前，$X$值比第$i$头牛小的个数；$len$为这些比$Xi$小的$X$值的和。

那么我们就要做树状数组同时维护两个值。

再来考虑另一半$X$比$i$大的怎么统计答案？

我们记录从$1 \sim i$的$X$的和，减去$len$，就可以计算出新的$len$。而新的$cnt$就可以直接用$i-cnt$计算得。

那么另一半的贡献就是$(len-cnt \times Xi) \times Vi$

这样我们就A了这题了。（学校的机子$O(N^2)$跑过去了什么鬼！）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
#include <iostream>
#include <algorithm>
#define Re register int
#define LL long long

struct Data{
	int V,X;
}d[20005];
int N,maxx,T[20005];
LL S[20005],Sum,ans;

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	var=w?-x:x;
}
inline int lowbit(int x) {return x&-x;}
inline int max(int a,int b) {return a>b?a:b;}
inline bool cmp(Data a,Data b) {return a.V<b.V;}
inline void AddNum(int pos)
{
	for (Re i=pos; i<=maxx; i+=lowbit(i))
		++T[i],S[i]+=pos; return;
}
inline void Query(int pos,LL &cnt,LL &len)
{
	cnt=len=0;
	for (Re i=pos; i>0; i-=lowbit(i))
		cnt+=T[i],len+=S[i];
}
int main(int argc, char const *argv[])
{
	read(N); LL cnt,len;
	for (Re i=1; i<=N; ++i)
		read(d[i].V),read(d[i].X),maxx=max(maxx,d[i].X);
	std::sort(d+1,d+N+1,cmp);
	for (Re i=1; i<=N; ++i)
	{
		Sum+=d[i].X; AddNum(d[i].X);
		Query(d[i].X,cnt,len);
		ans+=(cnt*d[i].X-len)*d[i].V;
		cnt=i-cnt,len=Sum-len;
		ans+=(len-cnt*d[i].X)*d[i].V;
	} printf("%lld\n",ans);
	return 0;
}