Codeforces Round #624 (Div. 3) F. Moving Points 题解

第一次写博客，请多指教！

翻了翻前面的题解发现都是用树状数组来做，这里更新一个线段树+离散化的做法：

其实这道题是没有必要用线段树的，树状数组就能够解决。但是个人感觉把线段树用熟了会比树状数组更有优势一点

不多废话

http://codeforces.com/contest/1311/problem/F 题目链接

题意是给你一堆点的位置和他们运动的速度（可正可负），然后时间无限往后推的情况下问你他们之间所有点的最小距离之和。（不明白自行读题）

n的范围是2，200000；显然单纯的一个一个看是不行的，那么自然想到用树状数组或者线段树来做。

接着可以想到

1.当两个点的位置xi ，xj满足 xi<xj 并且两个点的速度满足vi <=vj时他们之间的最短距离一定是当前距离即xj与xi之差。

2.其余情况最短距离均为零（这一点很容易想）

那么就好办了

思路就是

1.先对每个点对按照位置从小到大进行排序

2.按照位置从前到后遍历这些点，进行建树。由当前点的速度确定在数组中的位置。

3.建树时每更新一个点之前可以求出这个点对答案的贡献即：

ans+=（数组中位于当前点前面的点的数量（速度小于当前点速度的点的数量）×当前点的位置）- 前面所有点的位置值的和。

代码中的公式为 ans+=s[i].x*querye(1,x,1,n,1)-query(1,x,1,n,1);

由于是按照位置从前到后的顺序上树的，所以不必担心出现比当前点位置靠后的点；

而关于统计速度小于当前点速度的点的数量维护了一个he数组查询用querye函数，而前面所有点的位置值的和则是最一般的线段树查询。

至于速度给的数据范围有点大，可以使用离散化将他们集中起来，以便作为下标进行更新。

上代码（代码虽然看起来不是很简短但是基本都是模块化操作，耐心看下来就会感觉很容易理解）

https://www.cnblogs.com/LH2000/category/1656597.html 这里有一些本人写的相关模板函数，可以用作参考。

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define rush! ios::sync_with_stdio(false);cin.tie(0);

 const int inf = 0x3f3f3f3f;

 const long long linf = 0x3f3f3f3f3f3f3f3f;

 const int maxn=;

 long long tree[maxn<<];  //线段树

 long long lsh[];   //离散化 数组

 long long he[maxn<<];

 struct trees{

     long long x, v;

 }s[];

 bool cmp(const trees &x,const trees &y)

 {

     return x.x<y.x;

 }

 void pushup(int rt)

 {

     tree[rt]=tree[rt<<]+tree[rt<<|];    //用子节点更新父节点的位置值

     he[rt]=he[rt<<]+he[rt<<|];      //用子节点更新父节点数量值

 }

 void update(long long p,long long add,int l,int r,int rt)  //上树

 {

     if(l==r)

     {

         tree[rt]+=add;//更新位置值

         he[rt]++;//更新数量值

         return;

     }

     int m=(l+r>>);

     if(p<=m) update(p,add,lson);

     else update(p,add,rson);

     pushup(rt);

 }

 long long query(int L,int R,int l,int r,int rt) //查询速度小于当前点速度的元素位置值的和

 {

     if(L<=l&&r<=R)

     {

         return tree[rt];

     }

     int m=(l+r)>>;

     long long ret=;

     if(L<=m) ret+=query(L,R,lson);

     if(R>m) ret+=query(L,R,rson);

     return ret;

 }

 long long querye(int L,int R,int l,int r,int rt) //查询速度小于当前点速度的元素数量

 {

     if(L<=l&&r<=R)

     {

         return he[rt];

     }

     int m=(l+r)>>;

     long long ret=;

     if(L<=m) ret+=querye(L,R,lson);

     if(R>m) ret+=querye(L,R,rson);

     return ret;

 }

 int main()

 {

         rush! //加速流

         int n;

         cin>>n;

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

         {

             cin>>s[i].x;

         }

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

             cin>>s[i].v;

             lsh[i]=s[i].v;

         }

         sort(lsh+,lsh+n+);     //离散化排序

         sort(s+,s+n+,cmp);

         int cnt=unique(lsh+,lsh+n+)-lsh-;   //离散化数数

         long long ans=;

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

         {

             long long x=lower_bound(lsh+,lsh+cnt+,s[i].v)-lsh;   //离散化

             ans+=s[i].x*querye(,x,,n,)-query(,x,,n,);

             update(x,s[i].x,,n,);  //上树

         }

         cout<<ans<<endl;

 }

巴特西

Codeforces Round #624 (Div. 3) F. Moving Points 题解

最新文章

热门文章