总是有 $r_i=i$，并且 $l_i \leq l_{i+1}$（否则将 $l_i$ 调整成 $l_{i+1}$ 肯定更优。）
所以跑一遍决策单调性分治即可。比较子串大小用哈希 + SA，总复杂度 $\Theta(n \log n)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
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.