洛谷P2345 MooFest G

题目背景
P5094 [USACO04OPEN] MooFest G 加强版

题目描述
约翰的 nn 头奶牛每年都会参加“哞哞大会”。

哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。

它们参加活动时会聚在一起，第 ii 头奶牛的坐标为 x_ix
i
​
，没有两头奶牛的坐标是相同的。

奶牛们的叫声很大，第 ii 头和第 jj 头奶牛交流，会发出 \max{v_i,v_j}\times |x_i − x_j |max{v
i
​
,v
j
​
}×∣x
i
​
−x
j
​
∣ 的音量，其中 v_iv
i
​
和 v_jv
j
​
分别是第 ii 头和第 jj 头奶牛的听力。

假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。

输入格式
第一行：单个整数 nn，1\le n\le2\times 10^41≤n≤2×10
4

第二行到第 n + 1n+1 行：第 i + 1i+1 行有两个整数 v_iv
i
​
和 x_ix
i
​
（1\le v_i,x_i\le2\times 10^41≤v
i
​
,x
i
​
≤2×10
4
）。

输出格式
单个整数：表示所有奶牛产生的音量之和

输入输出样例
输入 #1复制
4
3 1
2 5
2 6
4 3
输出 #1复制
57
上代码：

#include
#include
using namespace std;
template<class T>inline void read(T&a){
	char c=getchar();int f=1;a=0;
	while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
	while(c<='9'&&c>='0') a=(a<<1)+(a<<3)+c-48,c=getchar();
	a*=f;
}
template<class T>void write(T a){
	if(a<0) putchar('-'),a=-a;
	if(a>9) write(a/10);
	putchar(a%10+48);
}
const int o=1e5+10;
long long n,x[o],v[o],p[o],q[o],ans,s1[o],s2[o];
inline bool cmp(int A,int B){return v[A]<v[B];}
inline bool cmp2(int A,int B){return x[A]<x[B];}
void cdq(long long p[],long long N){
	if(N==1) return;
	int md=N>>1,i,j;
	cdq(p,md);cdq(p+md,N-md);
	for(i=1;i<=N;++i) q[i]=p[i];
	sort(p+1,p+md+1,cmp2);sort(p+md+1,p+N+1,cmp2);
	for(i=md+1;i<=N;++i) s1[i-md]=s1[i-md-1]+v[p[i]],s2[i-md]=s2[i-md-1]+v[p[i]]*x[p[i]];
	for(i=1,j=md+1;i<=md&&j<=N;)
		if(x[p[i]]<x[p[j]]) ans+=x[p[i]]*(2*s1[j-md-1]-s1[N-md])-2*s2[j-md-1]+s2[N-md],++i;else ++j;
	if(j==N+1) for(;i<=md;++i) ans+=x[p[i]]*(2*s1[j-md-1]-s1[N-md])-2*s2[j-md-1]+s2[N-md];
	for(i=1;i<=N;++i) p[i]=q[i];
}
int main(){
	read(n);
	for(int i=1;i<=n;++i) read(v[i]),read(x[i]),p[i]=i;
	sort(p+1,p+1+n,cmp);
	cdq(p,n);
	write(ans);
	return 0;
}
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