E - Parenthesis Candidate
Darjeeling
2
s
1024
MB
600
点
問題文
( と * からなる長さ $N$ の文字列 $S$ が与えられます。$S$の空でない連続部分文字列で『括弧列の候補』となる文字列の個数を求めてください。
ただし、括弧列の候補とは以下の条件をみたす文字列のこととします。
(と*からなる文字列で、*をそれぞれ適切に(か)に変更することで、正規の括弧列となるもの
また、文字列として同じでも取り出した位置が異なる場合は区別して数えます。
正規の括弧列の定義
正規の括弧列とは、次のいずれかの条件を満たすものと定義します。
()- 正規の括弧列 $A$ が存在し、
(, $A$,)をこの順に結合した文字列 - 空でない正規の括弧列 $S$, $T$ が存在し、$S$, $T$ をこの順に結合した文字列
制約
- $1\leq N \leq 10^6$
- $S$ は
(と*からなる長さ $N$ の文字列 - $N$ は整数
入力
入力は以下の形式で標準入力から与えられる。
$N$
$S$
出力
答えを1行に出力してください。
入力例 1
6
(**(*(
出力例 1
4
$S$ の $l$ 文字目から $r$ 文字目を取り出した部分文字列を $S[l, r]$ とおくとき、 $S[2, 5] =$ **(* は括弧列の候補です。
具体的には、3つの * をそれぞれ (, ), ) に置き換えることにより、正規の括弧列 ()() を作ることができます。
括弧列の候補はほかに $S[1, 2] =$ (*, $S[2, 3] =$ **, $S[4, 5]=$ (* が存在し、合わせて4通りです。
入力例 2
10
(*(*(*(*(*
出力例 2
15