题目翻译

给定长度为 $n$ 的字符串 $s$ 以及 $l,r$。

对于所有 $k\in[l,r]$ 求出将 $s$ 分成 $k$ 段后每段的 LCP 最大值。

LCP 是最长公共前缀。

$1\leq n\leq 2\times 10^5,1\leq l\leq r\leq n$。多测。$1\leq \sum n \leq 2\times 10^5$。

题目思路

这一问需要求出很多 $l,r$。那么对于这类问题，往往是 $i$ 的答案可以推导出 $i+1$ 的答案，或者有一部分答案是一样的，需要你找出这个连续段。

考虑到我 duel 到的 CF786C 这题和这题做法完全一样就做完了。

但这题做法确实与 CF786C 一样。我慢慢说。

我们观察样例发现，最后总是有连续的相同段。大胆猜测这个就是关键。

考虑到对于 $k\geq B$ 的部分，一定存在 $|\operatorname{LCP}|\leq n/B$。

也就是说，如果我们取 $B=\sqrt n$，那么 对于 $k\geq \sqrt n$ 的部分只有 $\sqrt n$ 种答案。也就是会存在很多位置的 LCP 是一样的。

那么对于 $k\gt B$，我们先算一个答案，然后二分后面部分的位置找到最远的答案和自己一样的点。

喜报，上面划掉的做法复杂度和 $k\leq B$ 复杂度一样，常数过大我 ST 死掉了。

不这么做，考虑对于每个 LCP 长度，找到能分多少段，打个标记，之后做一个后缀 max。复杂度更优。

对于 $k\leq B$，直接做 G1 的单测即可。

代码链接

https://codeforces.com/contest/1968/submission/259503068

写得很丑。第一发 Hacked 是因为赛时卡常卡到一半莫名其妙过了。后来改了一发 Hash 的随机 Base。然后请群友把第一发叉了。锻炼 Hack 能力（雾）。