对于官方题解中的 “解法2”，经过猜测，$\max$ 的参数取的哪项是单调的。即一段前缀取第一项，之后取第二项。
所以使用可持久化平衡树寻找决策分界点即可。这样瓶颈在双平衡树二分，故复杂度为 $O(n\log^2 n)$。空间复杂度通过一些优化反正可以做到线性。
https://qoj.ac/submission/1809230
如果这个猜测是错误的，恳请赐教。如果您可以证明正确性，亦恳请赐教。
QOJ.ac
QOJ
The 3rd Universal Cup Finals is coming! Join our Warm-up Game and Prediction Game and win the prizes! Learn more...
Discussion #1504 for Problem #15508. 复读机
Type: Editorial
Status: Open
Posted by: incent
Posted at: 2026-04-12 18:37:14
Last updated: 2026-04-12 18:45:46
O(n\log^2 n) 做法
Comments
No comments yet.