洛谷P5094 MooFest G 加强版

题目描述
每一年，约翰的 NN 只奶牛参加奶牛狂欢节。这是一个全世界奶牛都参加的大联欢。狂欢节包括很多有趣的活动，比如干草堆叠大赛、跳牛栏大赛，奶牛之间有时还相互扎屁股取乐。当然，她们会排成一列嚎叫，来欢庆她们的节日。奶牛们的叫声实在刺耳，以致于每只奶牛的听力都受到不同程度的损伤。现在告诉你奶牛 ii 的听力为 v_iv
i
​
，这表示如果奶牛 jj 想说点什么让她听到，必须用高于 v_i \times dis(i,j)v
i
​
×dis(i,j) 的音量。因此，如果奶牛 ii 和 jj 想相互交谈，她们的音量必须不小于 \max (v_i,v_j) \times dis(i,j)max(v
i
​
,v
j
​
)×dis(i,j)。其中 dis(i,j)dis(i,j) 表示她们间的距离。

现在 NN 只奶牛都站在一条直线上了，每只奶牛还有一个坐标 x_ix
i
​
。如果每对奶牛都在交谈，并且使用最小音量，那所有 N(N-1)/2N(N−1)/2 对奶牛间谈话的音量之和为多少？

输入格式
第 11 行输入一个整数 NN 。

接下来 NN 行，每行输入两个数 v_iv
i
​
和 x_ix
i
​
，分别代表第 ii 头奶牛的听力和坐标。

输出格式
输出一个数，代表这 N(N-1)/2N(N−1)/2 对奶牛谈话时的音量之和。

输入输出样例
输入 #1复制
4
3 1
2 5
2 6
4 3
输出 #1复制
57
说明/提示
数据范围
因为原数据下 O(N^2)O(N
2
) 算法可以通过，所以新添加了一些增强数据。

原数据作为子任务 11，新添加的数据作为子任务 22。

子任务 11（11 分）：1 \leq N,V_i,x_i \leq 2 \times 10^41≤N,V
i
​
,x
i
​
≤2×10
4
。
子任务 22（9999 分）：1 \leq N,V_i,x_i \leq 5 \times 10^41≤N,V
i
​
,x
i
​
≤5×10
4
。
上代码：

#include
using namespace std;
const long long N=50005;
struct cow{
	long long v,p;
	bool operator<(const cow& c) const{
		return p<c.p;
	}
}a[N];
long long n,m,lb[N],c1[N],c2[N],caozuo,p,q,u,ans;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}//快读，其实没有必要，导致TLE的是下面一个地方的死循环
void add1(long long x,long long y)
{
	while(x<=N)//是N，因为树状数组长度并不是n，下面同理
	{
        c1[x]+=y;
        x+=lb[x];
	}
}
void add2(long long x,long long y)
{
    while(x<=N)
	{
        c2[x]+=y;
        x+=lb[x];
	}
}
long long sum1(long long x){
	long long res=0;
	if (x==0)
	{
		return 0;
	}
	for (;x>0;x-=lb[x])
	{
		res+=c1[x];
	}
	return res;
}
long long sum2(long long x){
	long long res=0;
	if (x==0)
	{
		return 0;
	}
	for (;x>0;x-=lb[x])
	{
		res+=c2[x];
	}
	return res;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=N;i++)//注意这里要是N，不然会在add里加0导致死循环TLE
   {
      lb[i]=i&(-i);
   }
	for(long long i=1;i<=n;i++)
	{
		a[i].v=read();
		a[i].p=read();
	}
	sort(a+1,a+n+1);//先按位置sort一遍。sort结构体在上面重载了运算符
	for (long long i=1;i<=n;i++){
		long long der=a[i].p*sum2(a[i].v)-sum1(a[i].v);
		ans+=der*a[i].v;
		add1(a[i].v,a[i].p);
		add2(a[i].v,1);//c2每次++
	}
	for(long long i=1;i<=N;i++)
	{
		c1[i]=0;
		c2[i]=0;
	}
	for (long long i=n;i>=1;i--){
		long long der=sum1(a[i].v-1)-a[i].p*sum2(a[i].v-1);
		ans+=der*a[i].v;
		add1(a[i].v,a[i].p);
		add2(a[i].v,1);
	}
	cout<<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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89