题解 P5471 【[NOI2019]弹跳】

## 题目大意 给出二维平面上的 $n$ 个整点 $(x_i,y_i)$ ，满足 $1\le x_i\le w,1\le y_i\le h$ 。按给出顺序编号为 $1,2,...,n$ 。有 $m$ 次连边操作，每次操作给定 $p,t,L,R,D,U$ ，从结点 $p$ 到满足条件 $L\le x_i\le R,D\le y_i\le U$ 的所有这样的结点 $i$ 连接一条边权为 $t$ 的有向边。求在所有连边操作结束后，从编号为 $1$ 的点到其他点的最短路长度。 $1\le w,h\le n\le 70000,1\le m\le 150000,1\le t_i\le 10000$ ### 32pts 暴力连边，边数最多为 $O(nm)$ ，跑最短路。 ~~暴力分还挺多~~ ### $L_i=R_i,D_i=U_i$ 观察到每次连边操作只会连接两个结点，暴力连边，边数为 $O(m)$ ，跑最短路。 什么，还有其他最短路算法？ ### $h=1$ 开题一看，这不是 **线段树优化建图** 的题吗？ 线段树优化建图，是图论问题中的经典技巧。将所有点按照 $x$ 坐标排序，观察到每次连边操作连接到的点都是连续的一段。  （图片来源： NaCly_Fish ） 我们对排序后的序列建一棵线段树，线段树上的每个结点向其左右儿子连一条边权为 $0$ 的边，每个叶子结点向其对应位置的点连一条边权为 $0$ 的边。在进行连边操作时，用类似于线段树上区间查询的方式向所有对应的点连一条边。根据线段树的经典结论，这样所连的边数最多是 $O(\log_2 n)$ 的。  总点数为 $O(n)$ ，总边数为 $O(n+m\log_2 n)$ ，可以存下所有的边，跑最短路即可。 线段树优化建图的经典题目： [CF786B Legacy](https://codeforces.com/problemset/problem/786/B) [P5025 \[SNOI2017\]炸弹](https://www.luogu.org/problemnew/show/P5025) ### 100pts 现在连边从原来的一维变成二维的了。 在做这题时，我考虑了分块套分块，分块套线段树，线段树套线段树等多种方法，最后发现线段树套动态开点线段树比较优秀。 外层 $x$ 坐标用普通线段树，这棵线段树上每个结点都对应一个关于 $y$ 坐标的线段树，线段树上存储的是所有 $x$ 坐标在范围内的点。由于内层动态开点线段树插入一个值的空间复杂度为 $O(\log_2 n)$ ，外层线段树有 $O(\log_2 n)$ 层，所以总的点数为 $O(n\log_2^2 n)$ 。 连边时，先找到 $O(\log_2 n)$ 个关于 $x$ 坐标的区间对应的点，然后对这 $O(\log_2 n)$ 棵线段树查询下标范围在 $y$ 坐标范围内的值。单次连接的边数为 $O(\log_2^2 n)$ ，总的边数为 $O(m\log_2^2 n)$ 。 然而，这种写法的内存使用超过了限制。一般的实现可以得到 $64$ 到 $72$ 分。有以下两个优化方法： 1. 树套树内层使用 $n$ 个结点时空间复杂度是 $O(n)$ 的 `set` 容器； 2. **不直接连边** 。回顾 Dij 的算法流程，有如下写法：用线段树套 `set` 维护一个矩阵中存在的整点，开始时扩展 $1$ 号结点的所有出边（直接连接到一个矩阵），每次取出优先队列中时间最小的一个矩阵，遍历矩阵中的每一个存在的整点，记录到这些点的最短路，扩展这些结点，然后在线段树套 `set` 上删除这些结点。由于每个结点只会被删除和扩展一次，所以这样做的时间复杂度是 $O(n\log_2^2 n)$ 的。 同时使用两种优化，时间复杂度是 $O(n\log_2^2 n)$ ，空间复杂度是 $O(n\log_2 n+m)$ 的，可以通过本题。 ## 代码展示 ```cpp #include<cstdio> #include<cstring> #include<algorithm> #include<set> #include<vector> #include<queue> using namespace std; const int maxn=150010; int n,m,W,H; struct city{int id,x,y;bool operator<(city a)const{return y==a.y?id<a.id:y<a.y;};}s[maxn]; set<city>st[maxn*2]; #define lc (o<<1) #define rc (o<<1|1) void update(int o,int l,int r,int v) { st[o].insert(s[v]); if(l==r)return; int mid=(l+r)>>1; if(s[v].x<=mid)update(lc,l,mid,v); else update(rc,mid+1,r,v); } void deleet(int o,int l,int r,int v) { st[o].erase(s[v]); if(l==r)return; int mid=(l+r)>>1; if(s[v].x<=mid)deleet(lc,l,mid,v); else deleet(rc,mid+1,r,v); } struct jumpy{int p,t,l,r,d,u;}e[maxn]; vector<int>g[maxn]; struct node{int x,v;bool operator<(node a)const{return v>a.v;};}x; priority_queue<node>q; queue<int>tag; int dist[maxn]; bool tf[maxn]; void erasse(int o,int l,int r,int id,int v) { int ql=e[id].l,qr=e[id].r; if(r<ql||l>qr)return; if(ql<=l&&r<=qr) { set<city>::iterator lb=lower_bound(st[o].begin(),st[o].end(),(city){0,n+1,e[id].d}); for(;lb!=st[o].end()&&(lb->y)<=e[id].u;lb++) { dist[lb->id]=v;tag.push(lb->id); for(vector<int>::iterator it=g[lb->id].begin();it!=g[lb->id].end();it++)q.push({*it,v+e[*it].t}); } while(!tag.empty())deleet(1,1,n,tag.front()),tag.pop(); return; } int mid=(l+r)>>1; erasse(lc,l,mid,id,v);erasse(rc,mid+1,r,id,v); } int main() { scanf("%d%d%d%d",&n,&m,&W,&H); for(int i=1;i<=n;i++)scanf("%d%d",&s[i].x,&s[i].y),s[i].id=i,update(1,1,n,i); for(int i=1;i<=m;i++)scanf("%d%d%d%d%d%d",&e[i].p,&e[i].t,&e[i].l,&e[i].r,&e[i].d,&e[i].u),g[e[i].p].push_back(i); e[0].l=e[0].r=s[1].x;e[0].d=e[0].u=s[1].y; q.push({0,0}); while(!q.empty()) { x=q.top();q.pop(); if(tf[x.x])continue; tf[x.x]=true; erasse(1,1,n,x.x,x.v); //for(vector<int>::iterator it=g[x.x].begin();it!=g[x.x].end();it++)q.push({e[*it].p,x.v+e[*it].t}); } for(int i=2;i<=n;i++)printf("%d\n",dist[i]); return 0; } ```