web analytics

Parenthesis ST表 括号匹配问题

题目就是问将一个匹配的括号序列的两个交换,新括号序列匹不匹配。每次查询不影响下次查询,所以这就是离线查询,区间RMQ问题。

题目:https://ac.nowcoder.com/acm/contest/1112/G

为什么是RMQ呢?

(一般的括号匹配问题)用到了前缀和思想,左括号加一,右括号减一。只需要判断前缀和是否大于0,就可以判断括号是否匹配。

但是这里,因为有交换,所以我们在发现,如果交换的括号是'(”)’的时候,该区间内的所有前缀和会-2,所以我们判断合法就可以查该区间内最小值,如果最小值大于2,则合法,反之。

所以用ST表就可以解决这个问题。