地牢游戏 题解 首先，我们根据 s u b t a s k   3 , 4 subtask\,3,4 subtask3,4，应该很容易想到一种倍增的做法去解决我们的问题。 对于这几个图，我们的分层是相当少的，所以我们可以将我们整个过程分成至多 6 6 6个阶段，对于每个阶段单独倍增直到超越这个阶段，或者说抵达我们的终点。 我们考虑将我们的倍增做法延伸到我们的正解上，显然，由于当我们胜利后会

https://www.luogu.com.cn/problem/P8518 没有要求在线，显然离线（。维护时间戳，上线段树。 好了，我们现在知道一个人的曲线变化了。怎么做呢？ 前面所有碰上下界的都是没用的！我们只需要找最后一段的时间段满足差值为 c i c_i ci​即可。因为差值更大的我们显然可以最后又会规约成这种情况。 关于差值的维护，我们维护后缀min/max，然后线段树上二分即