外观
2026-07-24
考试的时候想到了 aaa、想到了分治,但是没发现 bbb。。。
考虑给左括号赋值为 111,右括号为 −1-1−1,做其前缀和存在 aaa 里,显然,一个括号序列可行的条件是所有的 a≥0a\geq 0a≥0。 事实上,对于区间 [l,r][l,r][l,r],将其翻转等价于关于序列中点中心对称,也就是我们只需要考虑最小的 ai≥0a_i\geq 0ai≥0 即可,写出来就是 al−1+ar−maxi=l−1raia_{l-1}+a_r-\max_{i=l-1}^r a_ial−1+ar−maxi=l−1rai
版权归属:lyrgo
许可证:署名 4.0 国际 (CC-BY-4.0)