A.括号序列
-
一看，我趣，字符串，直接抱灵吧，让我死得体面一点……
-
再一看数据范围，我趣，\(\mathtt{O(n)}\)，这怎么写得出来啊？
Solution
-
虽然是 \(\mathtt{O(7n)}\)，但卡卡常也就卡过了；
-
先遍历一遍，把括号两两匹配一下，记录一下另一半括号的位置。再来两边 \(\mathtt{O(n)}\)，处理出可以形如 \(\mathtt{()()}\) 这样合并的括号个数的前缀和（\(sum_0\)）与后缀和（\(sum_1\)）；
-
然后一遍 \(\mathtt{O(n)}\)，统计上面这种方式合并每个位置的答案（为 \((sum_{0,i}-1)\times(sum_{1,pos_i}+1)\)）。
-
考虑如何处理括号套括号的情况。