[洛谷 5471,loj 3159][NOI2019]弹跳

题目链接

https://www.luogu.com.cn/problem/P5471

https://loj.ac/problem/3159

题解

测试点 1-13

这些测试点中,暴力连边跑最短路的时间和空间复杂度(当然前提是你得用最坏复杂度可以通过的最短路算法)可以接受。

建图的时间复杂度:

  • 测试点 \(1 \sim 8\):\(O(n^2)\);
  • 测试点 \(9 \sim 13\):\(O(n \log n)\)。

测试点 14-18

平面退化成了直线,而我们连边总是从某个点连向在某个区间内的所有点。考虑使用线段树优化建图

我们先建出线段树,其中树上的每个点向其两个子节点各连一条边权为 \(0\) 的边,每个叶子节点向其对应的真实节点连一条边权为 \(0\) 的边。

建图的方式和线段树维护区间信息差不多,我们只需向线段树上能覆盖对应区间的点连边即可。和线段树维护区间信息一样,我们一次最多连 \(O(\log n)\) 条边。

因此我们连的总边数为 \(O(n+m \log n)\)。

满分做法

现在考虑二维平面上的问题。

考虑在线段树套线段树上建图。和一维的情况类似,我们先在外层查询满足 \(x\) 范围的点,再在内层查询满足 \(y\) 范围的点来建图即可。

树套树的空间复杂度为:\(O(n \log^2 n)\)。连边的总数为 \(O(m \log^2 n)\)。因为本题空间限制较小,上面的做法无法通过本题。

如何优化空间?

可以将内层的线段树换成 set。从而数据结构的空间复杂度为 \(O(n \log n)\)。

更棒的是,我们实际上可以不将边连出来,从而省下了建图的空间。

不建图怎么求最短路?直接利用已有的弹跳装置的信息来更新最短路。

我们回想一下 Dijkstra 求最短路的性质。我们每次从堆顶取出的点,其最短路已经是确定的,不会再更新。

设从 \(1\) 号点经过第 \(i\) 个弹跳装置的最短路为 \(w_i\),我们先将从 \(1\) 开始的所有装置扔进堆里。

从堆中取出 \(w_i\) 最小的装置(根据上文所述,这个装置的 \(w_i\) 不会再更新),在线段树套 set 里查询当前装置能到达的点,将这些点的最短路更新为 \(w_i\),随后将这些点从数据结构里删除(根据上面的描述,这些点的最短路不会再更新)。与此同时,我们更新经过当前装置能直接到达的装置的 \(w_i\) 值。

#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
struct point
{
 int x,y,id;
 bool operator<(const point&a)const
 {
  return y<a.y||(y==a.y&&x<a.x);
 }
}p[70005];
struct edge
{
 int p,t,l,r,d,u;
}e[150005];
struct node
{
 int u,dis;
 bool operator>(const node&a)const
 {
  return dis>a.dis;
 }
};
vector<int> f[70005];
set<point> s[300005];
priority_queue<node,vector<node>,greater<node> > q;
int dis[70005],vis[150005];
int n,m,w,h;
void add(int root,int l,int r,int x)
{
 s[root].insert(p[x]);
 if(l==r)return;
 int mid=(l+r)>>1;
 if(p[x].x<=mid)add(root<<1,l,mid,x);
 else add(root<<1|1,mid+1,r,x);
}
void del(int root,int l,int r,int x)
{
 s[root].erase(p[x]);
 if(l==r)return;
 int mid=(l+r)>>1;
 if(p[x].x<=mid)del(root<<1,l,mid,x);
 else del(root<<1|1,mid+1,r,x);
}
void modify(int root,int cl,int cr,int x,int d)
{
 queue<int> dq;
 int l=e[x].l,r=e[x].r;
 if(cr<l||r<cl)return;
 if(l<=cl&&cr<=r)
 {
  auto it=s[root].lower_bound((point){0,e[x].d,0});
  //在线段树套 set 里找每个装置能到达的点
  for(;it!=s[root].end()&&it->y<=e[x].u;it++)
  {
   int u=it->id;
   dis[u]=d;//更新这些点的最短路
   dq.push(u);
   for(auto v:f[u])//将经过当前装置能到达的下一个装置插入堆
    q.push({v,d+e[v].t});
  }
  while(!dq.empty())//将这些点从数据结构中删除
  {
   int u=dq.front();
   dq.pop();
   del(1,1,n,u);
  }
  return;
 }
 int mid=(cl+cr)>>1;
 modify(root<<1,cl,mid,x,d);
 modify(root<<1|1,mid+1,cr,x,d);
}
int main()
{
 ios::sync_with_stdio(false);
 cin>>n>>m>>w>>h;
 for(int i=1;i<=n;i++)
 {
  cin>>p[i].x>>p[i].y;
  p[i].id=i;
  add(1,1,n,i);//将所有点扔进线段树套 set 里
 }
 for(int i=1;i<=m;i++)
 {
  cin>>e[i].p>>e[i].t>>e[i].l>>e[i].r>>e[i].d>>e[i].u;
  f[e[i].p].push_back(i);//维护从 i 号点出发的装置列表
 }
 e[0].l=e[0].r=p[1].x;
 e[0].d=e[0].u=p[1].y;
 q.push({0,0});
 while(!q.empty())
 {
  int u=q.top().u,d=q.top().dis;
  q.pop();
  if(vis[u])continue;//和 Dijkstra 一样,已经走过的装置不必再走
  vis[u]=1;
  modify(1,1,n,u,d);
 }
 for(int i=2;i<=n;i++)
  cout<<dis[i]<<endl;
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据