对于官方题解中的 “解法2”，经过猜测，$\max$ 的参数取的哪项是单调的。即一段前缀取第一项，之后取第二项。
所以使用可持久化平衡树寻找决策分界点即可。这样瓶颈在双平衡树二分，故复杂度为 $O(n\log^2 n)$。空间复杂度通过一些优化反正可以做到线性。
https://qoj.ac/submission/1809230
如果这个猜测是错误的，恳请赐教。如果您可以证明正确性，亦恳请赐教。
QOJ.ac
QOJ
Discussion #1504 for Problem #15508. 复读机
Type: Editorial
Status: Open
Posted by: incent
Posted at:
Last updated:
O(n\log^2 n) 做法
Comments
incent
以下为 hack 数据。正确输出倒数第二行为 1944
21 27
110100000000000000000000000 1
110010000000000000000000000 1
110001000000000000000000000 1
110000100000000000000000000 1
110000010000000000000000000 1
110000001000000000000000000 1
110000000100000000000000000 1
110000000010000000000000000 1
110000000001000000000000000 1
111100000000000000000000000 1
111010000000000000000000000 1
111001000000000000000000000 1
111000100000000000000000000 1
111000010000000000000000000 1
111000001000000000000000000 1
111000000100000000000000000 1
111000000010000000000000000 1
101111111111111111111111111 100
1 9
1 1
1 4