总是有 $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: 2026-01-29 20:05:55
Last updated: 2026-01-29 20:08:35
New Editorial for Problem #6624
Comments
No comments yet.