BZOJ2732/HNOI2011/括号修复

Posted on By 二价氢

#题目描述

#做法

将括号序列看成前缀序列,取(=1,)=-1

然后Splay维护以下四个值:

最大前缀,最小前缀,最大后缀,最小后缀

##Replace

打标记,查询时标记下传

##Swap

打标记,查询时标记下传

##Invert

打标记,查询时标记下传

好吧,要注意Replace如果在Invert的后面操作的话,Invert就能直接覆盖了

#复杂度分析

#AC Code