亟隐

朝不闻道,夕亦死可矣

05/28
20:48
算法区

UVALive 6838 Flipping Parentheses

地址:戳这里

每一个位置Sun[i]记录前缀中'(‘减去’)’数量只差,一个合法的序列满足两种括号数量一样,并且每个Sum[i]都不为负数。

如果改变的是'(‘,设为在第x个位置,那么下一个应该改变的就是最前面的’)’,设置第y个位置。只有i在[y,x]区间内时,Sum[i]才会改变。此时Sum[y]减少2,Sum[y]..Sum[x]都加上2,必然满足条件。

如果改变的是’)’,设为在第x个位置,那么修改的位置应该是最小的y,满足所有i属于[y,x]区间都大于等于2,因为把'(‘改变成’)’后面的Sum[]都应该减少2.

用线段树维护Sum[],用堆记录’)’的位置处理第一种情况,第二种情况二分后用线段树判断。复杂度O(Nlog^2N).

代码:戳这里