【题解】Luogu P5471 [NOI2019]弹跳

逃离我推掉我的手 2021-10-20 00:20 330阅读 0赞

[原题传送门][Link 1]

先考虑部分分做法：

### subtask1： ###

暴力\\(O(nm)\\)枚举，跑最短路

### subtask2: ###

吧一行的点压到vector中并排序，二分查找每一个弹跳装置珂以到达的城市，跑最短路

### subtask3： ###

看见是一个链，自然而然的可以想到线段树优化建图，跑最短路

### 100pts ###

上面是72pts的暴力做法，其中subtask3的做法给了我们了一些提示，这题要用数据结构优化建图：

在横轴上开一颗线段树，线段树每个节点上是一个存pair的set，存的是\\(\[l,r\]\\)区间内有第\\(id\\)个点(\\(px\[id\] \\in \[l,r\]\\))，这个点的纵坐标是\\(py\[id\]\\)（pair要把纵坐标放前面）

类似线段树优化建图，我们要创建一些虚拟节点：对于第\\(i\\)个弹跳装置，我们创建一个编号为\\(i+n\\)的虚拟点，且到虚拟点的距离为所用时间\\(T\[i\]\\)

我们从\\(1\\)号点跑最短路。假如现在对顶是\\(x\\)号节点，当\\(x \\leq n\\)时，我们更新起点为\\(x\\)的弹跳装置的虚拟点的dis，并扔进堆；否则就在线段树上先找到\\(\[L\[x-n\],R\[x-n\]\]\\)这个区间(\\(x-n\\)就是该虚拟点所对应弹跳装置的编号)，在这个区间所含的线段树节点上二分出\\(D\[x-n\] \\leq py\[id\] \\leq U\[x-n\]\\)中的节点，尝试更新dis，如果成功加入队列，不管成不成功，都从set中删除（根据dij的特性）。

这样最后输出dis\[2~n\]就行了

这个算法的复杂度是\\(O((n+m)\\log(n+m)+n\\log^2 n)\\),常数略(da)大(dao)一(mei)点(jiu)

(\\((n+m)\\log(n+m)\\)是\\(n+m\\)个点dij的复杂度，\\(n\\log^2 n\\)是\\(n\\)个节点，每个拆成\\(\\log n\\)个，在set中insert,lowerbound,erase的复杂度)

#include <bits/stdc++.h> #define N 70005 #define M 150005 #define getchar nc using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int read() { register int x=0,f=1;register char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f; } inline void write(register int x) { if(!x)putchar('0');if(x<0)x=-x,putchar('-'); static int sta[20];register int tot=0; while(x)sta[tot++]=x%10,x/=10; while(tot)putchar(sta[--tot]+48); } int n,m,w,h; int px[N],py[N]; int P[M],T[M],L[M],R[M],D[M],U[M]; set<pair<int,int> > s[N<<2]; vector<int> nv[N]; struct node{ int dis,pos; bool operator < (const node &x) const{ return x.dis<dis; } }; priority_queue<node> q; int dis[N+M],vis[N+M]; inline void modify(register int x,register int l,register int r,register int id) { s[x].insert(make_pair(py[id],id)); if(l==r) return; int mid=l+r>>1; if(px[id]<=mid) modify(x<<1,l,mid,id); else modify(x<<1|1,mid+1,r,id); } inline void change(register int x,register int l,register int r,register int id) { if(L[id]<=l&&r<=R[id]) { set<pair<int,int> >::iterator it; while(19260817) { it=s[x].lower_bound(make_pair(D[id],-1)); if(it==s[x].end()||it->first>U[id]) break; int to=it->second; if(dis[to]>dis[id+n]) { dis[to]=dis[id+n]; q.push((node){dis[to],to}); } s[x].erase(it); } return; } int mid=l+r>>1; if(L[id]<=mid) change(x<<1,l,mid,id); if(R[id]>mid) change(x<<1|1,mid+1,r,id); } int main() { n=read(),m=read(),w=read(),h=read(); for(register int i=1;i<=n;++i) { px[i]=read(),py[i]=read(); if(i!=1) modify(1,1,w,i); } for(register int i=1;i<=m;++i) { P[i]=read(),T[i]=read(),L[i]=read(),R[i]=read(),D[i]=read(),U[i]=read(); nv[P[i]].push_back(i+n); } for(register int i=1;i<=n;++i) dis[i]=1926081700,vis[i]=0; dis[1]=0; q.push((node){0,1}); while(!q.empty()) { node tmp=q.top(); q.pop(); int x=tmp.pos; if(vis[x]) continue; vis[x]=1; if(x<=n) { for(register int i=0;i<nv[x].size();++i) { int y=nv[x][i]; dis[y]=dis[x]+T[y-n]; q.push((node){dis[y],y}); } } else change(1,1,w,x-n); } for(register int i=2;i<=n;++i) write(dis[i]),puts(""); return 0; }

转载于:https://www.cnblogs.com/yzhang-rp-inf/p/11211581.html

[Link 1]: https://www.luogu.org/problemnew/show/P5471