总是有 $r_i=i$，并且 $l_i \leq l_{i+1}$（否则将 $l_i$ 调整成 $l_{i+1}$ 肯定更优。）
所以跑一遍决策单调性分治即可。比较子串大小用哈希 + SA，总复杂度 $\Theta(n \log n)$。
QOJ.ac
QOJ
Discussion #890 for Problem #6624. String Problem
Type: Editorial
Status: Open
Posted by: qqqaaazzz
Posted at:
Last updated:
New Editorial for Problem #6624
Comments
No comments yet.