codeforces 380 C. Sereja and Brackets (线段树区间合并)

题目链接
题意:给出一个由‘(’和‘)’组成的字符串。。。然后给出若干查询。。。每个查询一个区间,问区间中能匹配的括号数。。。

思路:考虑某一个区间中的括号匹配。。。其实是一个不断寻找'()’然后删去的过程。。。

因此对于某个区间的括号匹配数。。。等于左边区间和右边区间和合法匹配数之和,再加上左区间和右区间新的能匹配到一起的括号数。

(说“因此”是因为。。。只要左边有没匹配的左括号。。。右边有没匹配的右括号。。。因为他们中间有的都是匹配好的括号,会被删除。。。所以两边的括号总能匹配在一起)

具体做法是:

线段树的节点中有三个域,分别表示,合法的括号匹配数,没有被匹配的左括号数,和没有被匹配的右括号数。

query的时候要合并左右两个区间。。。不过可能某一区间中为空。。。这里合理得初始化为node(0,0,0),就不用分情况讨论了。。。

一个和node(0,0,0)合并对原来的答案没有影响。。。。

以及,凡是需要在query的时候合并区间的问题。。。(不是那种简单的sum,min/max合并)

返回一个node会方便很多。。。。。