概述
-
略。真让我一周把这些车出来不如~了我。
-
真想整的话就...
例题
P4155 [SCOI2015] 国旗计划
-
题意略。我一开始把题审错了以为是链...另外这里是要接力的，即覆盖的对象是段，而非点，也即接力的两个人必须有交集...
-
那么先谈谈我的假做法：直接前后缀贪，记录几个能到哪，于是前后二分即可。
-
然而上环之后我们注意到前后缀这种东西根本不存在：没有起点。
-
看了 tag 之后...嘛。设法将信息合并，或者说，设法让每个起点利用到其他起点算过的信息，即倍增：\(f_{step,i}\) 表示从 \(i\) 出发走 \(step\) 步最远到哪里。
-
于是好像问题显然了哦...在倍增数组上二分，呸，二进制拆分即可。
-
p.s.被这道题折磨了好久...这种破环成链乍一看是无限延伸的，保留环的话又会首尾循环（导致可能没在合适的地方停，直接跳过去了），但实际上用复制出来的第二份堵一下就好（指倍增右界）。