BZOJ3378:[USACO]MooFest 狂欢节(树状数组)

2022-11-21 16:05:19

Description

每一年，约翰的N(1≤N≤20000)只奶牛参加奶牛狂欢节．这是一个全世界奶牛都参加的大联欢．狂欢节包括很多有趣的活动，比如干草堆叠大赛、跳牛栏大赛，奶牛之间有时还相互扎屁股取乐．当然，她们会排成一列嚎叫，来欢庆她们的节日．奶牛们的叫声实在刺耳，以致于每只奶牛的听力都受到不同程序的损伤．现在告诉你奶牛i的听力为vi(l≤Vi≤20000)，这表示如果奶牛j想说点什么让她听到，必须用高于vi×dis(i，j)的音量．而且，如果奶牛i和j想相互交谈，她们的音量必须不小于max(Vi，Vj)×dis(i，j).其中dis(i，J)表示她们间的距离．

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

Input

第1行输入N，之后N行输入Vi和xi．

Output

输出音量之和．

Sample Input

4
3 1
2 5
2 6
4 3

Sample Output

Solution

首先把奶牛按听力排序，那么$max(vi,vj)~(j<i)$一定是$v_i$。问题变成了对于每个$i$，求它和前面奶牛的$dis$和。

开两个树状数组$A$和$B$，$A_i$表示下标为$i$的奶牛的坐标和，$B_i$表示下标为$i$的奶牛的个数，然后算一下就好了。

Code

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #define N (20009)

 #define LL long long

 using namespace std;

 int n;

 pair<int,int>a[N];

 LL ans,p1,q1,p2,q2;

 struct BIT

 {

     LL c[N];

     void Update(int x,int k)

     {

         for (; x<=; x+=(x&-x)) c[x]+=k;

     }

     LL Query(int x)

     {

         LL ans=;

         for (; x; x-=(x&-x)) ans+=c[x];

         return ans;

     }

 }A,B;

 inline int read()

 {

     int x=,w=; char c=getchar();

     while (c<'' || c>'') {if (c==-'-') w=-; c=getchar();}

     while (c>='' && c<='') x=x*+c-'', c=getchar();

     return x*w;

 }

 int main()

 {

     n=read();

     for (int i=; i<=n; ++i) a[i].first=read(), a[i].second=read();

     sort(a+,a+n+);

     for (int i=; i<=n; ++i)

     {

         int v=a[i].first,x=a[i].second;

         A.Update(x,x); B.Update(x,);

         LL p1=A.Query(x-),q1=B.Query(x-);

         ans+=v*(q1*x-p1);

         LL p2=A.Query()-A.Query(x),q2=B.Query()-B.Query(x);

         ans+=v*(p2-q2*x);

     }

     printf("%lld\n",ans);

 }

码农公寓