括弧列を高さに言い換えるパートです。

文字列 \(s\) の長さを \(n\) とおいて、「高さ」 \(h ( i ) \ ( i = 0, \dots , n )\) を

\[ h ( i )= \begin{cases} n & i = 0, \\ h (i - 1) + 1 & i \neq 0 \ \mathrm {and} \ s[i - 1] = \mathtt { ( }, \\ h (i - 1) - 1 & i \neq 0 \ \mathrm {and} \ s[i - 1] = \mathtt { ) } \\ \end{cases} \]

により定義しましょう。すると \(0 \le i \lt j \le n\) に対して文字列 \(s [i], \dots s[j - 1]\) が「括弧の対応が取れている文字列」になる条件は

\[ h ( i ) = h ( j ) \ \mathrm { and } \ \left (k \in \lbrace i, .., j \rbrace \Rightarrow h ( i ) \le h ( k ) \right ) \]

です。

数え上げパート

左から順に見て、そこまでにどの高さを何回見たのかを覚えておきましょう。ただし数えるのは「有効な」もの、すなわちそこから今までにそれよりも低い高さを見てしまうとよくありませんからそういうものの存在しないようなものに絞りましょう。

具体的には次のものを計算すると良いです。\(0 \le i \le n, 0 \le x \le 2 n\) に対して、

\[ a ( i, x ) = \# \left \lbrace j \in [ 0, i [ : h ( j ) = x \ \mathrm { and } \ h ( j ) \le h ( k ) \right \rbrace \]

と定義しましょう。するとこれは \(i\) が増えるごとに高々 2 箇所しか値が変わらずですから、DP 配列を使い回すことで高速化できます。そして答えは \(\sum _ { i = 0 } ^ n a ( i, h ( i ) )\) となり、最悪時間計算量 \(O ( n )\) を達成します。