gym102889J线段树维护最大最小前缀和判断合法括号序列
题目
给出一个括号序列,每次操作给出一个区间$[L:R]$,将区间内括号取反,并回答操作后整个括号序列还是否合法。
解题思路
将(
看做1 ,)
看做-1。得到新的数组$a_i$
一个括号序列合法的判断条件是在任意位置,a数组的前缀和为非负数,并且数组和为0。
线段树维护区间前缀最小值核心代码:
1 | tr[k].pre_min = min(tr[LSON].sum + tr[RSON].pre_min, tr[LSON].pre_min); |
AC代码
1 |
|