自动搬运

查看原文

来自洛谷，原作者为

	decoqwq **

搬运于2025-08-24 22:11:56，当前版本为作者最后更新于2020-01-13 21:16:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

比赛结束这么久一直忘了把官方题解放上来

题目归纳为，给定一个循环队列，每次比较队头的两个元素 $p1,p2$，距离当前指针的位置，如果 $p1$ 不比 $p2$ 远，令指针指向 $p1$, 并弹出队列，否则将 $p1$ 放回队尾 统计指针移动距离

模拟可以获得$30$分

因为每个元素只会出队一次，所以我们考虑优化寻找下一个出队元素的过程

考虑二分，但是这没有单调性啊，比如我可能在第 $i$ 个位置停下，却不一定 能在第 $i + 1$ 个位置停下啊。 换一种判断方式，如果我们会在区间 $[1, i]$ 中的某个位置停下， 就一定会在区间 $[1, i + 1]$ 的某个位置停下 所以如何判断对于当前指针 $s$，我们是否会在区间 $[1, i]$ 停下呢？

我们可以发现，对于相邻的两个元素 $pi, pi+1$，是可以找到一条，分界线的，其中分界线的一侧都会被拦下来，而另一侧都可以通过

我可以维护区间中分界线的交集！线段树即可

所以思路就是先二分，然后判断区间的交集是否能拦下从$s$ 处出发的老师

最终复杂度$O(nlog^2n)$

如果写了正解还是 $TLE$ 可能只是常数过大(，$std$ 没有加快读仍然只在 $2s$ 内完成了