[NOI2019]|[NOI2019] 弹跳 [NOI2019]弹跳

link
$solution:$ 大力线段树即可。
有一个简单做法为在每一个线段树的节点维护一个 $set$ ,线段树存 $x$ 轴， $set$ 维护 $y$ 轴，然后每次暴力取点 $dijkstra$ 即可。
因为线段树上最多 $n\log n$个点，在线段树上取点后还要删除此点,动态维护，不直接连边。
即空间复杂度 $O(n\log n)$ ，时间复杂度 $O(n\log^2 n)$ 。

文章图片

文章图片

#include #include #include #include #include #include using namespace std; inline int read(){ int f=1,ans=0; char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar(); } while(c>='0'&&c<='9'){ans=ans*10+c-'0'; c=getchar(); } return f*ans; } const int MAXN=150001; priority_queueint,int> > que; setint,int> > s[MAXN<<2]; int dis[MAXN<<2],vis[MAXN<<2],head[MAXN],cnt; struct spe{ int x,y; }g[MAXN]; struct Segment{ void modify(int k,int l,int r,int x,int y,int id){ s[k].insert(make_pair(g[id].y,id)); if(l==r) return; int mid=l+r>>1; if(x<=mid) modify(k<<1,l,mid,x,y,id); if(mid >:: iterator it; while(!s[k].empty()){ it=s[k].lower_bound(make_pair(L,-1)); if(it==s[k].end()||(*it).first>R) break; int v=(*it).second; if(dis[v]>dis[id]){ dis[v]=dis[id]; que.push(make_pair(-dis[v],v)); }s[k].erase(*it); } return; } int mid=l+r>>1; if(x<=mid) Query(k<<1,l,mid,x,y,L,R,id); if(midn){ segment.Query(1,1,w,f[xx-n].l,f[xx-n].r,f[xx-n].d,f[xx-n].u,xx); continue; } for(int i=head[xx]; i!=-1; i=x[i].nex){ int v=x[i].v+n; if(dis[v]>dis[xx]+f[x[i].v].w){ dis[v]=dis[xx]+f[x[i].v].w; que.push(make_pair(-dis[v],v)); } } }for(int i=2; i<=n; i++) printf("%d\n",dis[i]); return 0; }

View Code
【[NOI2019]|[NOI2019] 弹跳】转载于:https://www.cnblogs.com/si-rui-yang/p/11226654.html