题解：P14061 【MX-X21-T6】[IAMOI R5] 希望有羽毛和翅膀

· · 题解

固定 $k$ 时，发现回文串长度只能是 $k$ 或者 $k+1$，从 $l$ 开始贪心，对于两种情况只需要分别找到最近的，符合对应 $l'\ge l$ 的回文中心跳，取更近的作为这个 $r$ 跳过去。 按照 $k$ 进行扫描线，预处理所有奇偶回文中心，那么一段 $k$ 之后会删除某些中心，相当于维护一个集合 $S$，支持删除 $x\in S$，或者给定 $x$ 查询最小的 $y\in S,y\ge x$。这一步可以 $\sqrt n$ 删除，$\mathcal O(1)$ 查询：对序列分块，维护块内后继以及块间后继，重构复杂度 $\sqrt n$。又因为答案不超过 $\frac{n}{k}$，所以 $k>B$ 时直接暴力跳即可；$k\leq B$ 时处理每个点后继，求 $l$ 开始多少步可以到达 $r$。注意预处理只能线性，因此同样序列分块，处理块内后继以及块外首个后继与对应步数，查询的代价是 $\mathcal O(\sqrt n)$。如果使用倍增，那么预处理的复杂度会多 $\log$。 视 $n,q$ 同阶，总时间复杂度 $\mathcal O(n\sqrt n)$。