洛谷——P2657 低头一族

https://www.luogu.org/problem/show?pid=2657

题目描述

一群青年人排成一队，用手机互相聊天。

每个人的手机有一个信号接收指标，第i个人的接收指标设为v[i]。

如果位置在x[i]的人要和位置在xj的人聊天，那么这两人组成的一对的信号发射强度就是abs(x[i]-x[j])*max(v[i],v[j]).

现在我们想知道，这些人所有对子中的信号发射强度的总和。

输入输出格式

输入格式：

第一行一个整数N，接下来N行，每行两个整数v[i]和x[i]。

输出格式：

所有对的信号发射强度总和。

输入输出样例

输入样例#1：

输出样例#1：

说明

对于40%的数据，N<=5,000

对于100%的数据，N<=100,000 1≤x[i]≤20,000

[color=red]注意：可能有两人在同一个位置

答案在int64或long long范围内[/color]

对于公式 abs(x[i]-x[j])*max(v[i],v[j]). 先给年轻人排队，让V小的在前面

用树状数组维护第i个人的前面有多少人的x比他的小，维护前面比他小的x的人的x的总和

 #include <algorithm>

 #include <cstdio>

 #define LL long long

 const int N(+);

 LL n,ans;

 struct Node {

     LL val,pos;

     bool operator < (const Node &x)const

     {

         return val<x.val;

     }

 }people[N];

 inline void read(LL &x)

 {

     x=; register char ch=getchar();

     for(;ch>''||ch<'';) ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-'';

 }

 #define max(a,b) (a>b?a:b)

 LL maxpos,sum[N],num[N];

 #define lowbit(x) (x&((~x)+1))

 inline void Update(LL *tr,LL i,LL x)

 {

     for(; i<=maxpos; i+=lowbit(i)) tr[i]+=x;

 }

 inline LL Query(LL *tr,LL i)

 {

     LL ret=;

     for(; i; i-=lowbit(i)) ret+=tr[i];

     return ret;

 }

 int AC()

 {

     read(n);

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

     {

         read(people[i].val);

         read(people[i].pos);

         maxpos=max(maxpos,people[i].pos);

     }

     std::sort(people+,people+n+);

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

     {

         LL pos=people[i].pos,val=people[i].val;

         LL numl=Query(num,pos-);

         LL suml=Query(sum,pos-);

         LL numr=Query(num,maxpos)-Query(num,pos);

         LL sumr=Query(sum,maxpos)-Query(sum,pos);

         ans+=val*(pos*numl-suml+sumr-pos*numr);

         Update(num,pos,); Update(sum,pos,pos);

     }

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

     return ;

 }

 int Hope=AC();

 int main(){;}

巴特西

洛谷——P2657 低头一族

https://www.luogu.org/problem/show?pid=2657

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章