外观
贪心
2026-10-21
翻译一下原题面,对于一个合法括号序列,考虑如何计算变长时的答案。 发现可以维护一个大根堆,由于最后一位必须为 ),每个奇数位置,我们可以贪心的选择一个新的 (,此时在未使用的 www 中取最大值即可。
)
(
现在就可以考虑如何处理操作了,注意到 111 和 333 等价于新增一组,只需要取最大值加在答案里即可,考虑如何处理 222 操作。 由于 222 操作在前后都加一个,相当于改变了奇偶性,只需要针对两种奇偶记录两个答案 ans0,ans1ans_0,ans_1ans0,ans1,简单维护即可。
版权归属:lyrgo
许可证:署名 4.0 国际 (CC-BY-4.0)