首先考虑有哪些站点是可达的:若站点 y(x<y)y\,(x<y) 是可达的,则中间的每一个站点都一定是可达的(因为可以在中途切换火车轨道)。求出可达的站点区间 [l,r](lxr)[l,r]\,(l\le x\le r) 后,区间 [x+1,r][x+1,r] 中的轨道右端点和区间 [l,x1][l,x-1] 中的左端点是可能的终点。

如何求出可达区间?下面以右端点 rr 为例。在火车往右行驶时,从右端点较小的轨道切换到右端点较大的轨道更优,这启发我们按照右端点从小到大处理每个轨道,同时维护右端点 rr:如果 rr 能到达这个轨道且轨道的右端点大于 rr,则更新 rr 的值。

时间复杂度 O(nlogn)O(n\log n)

0 comments

No comments so far...