概要
問題文 → ■
公式解説 → 存在するか分からず
自分の提出 → ■
出典は Gennady Korotkevich Contest 1 (Petrozavodsk Summer 2013) だと思われますが，解説がどこかに存在するのかが分かりませんでした．
解法
問題文を要約すると次の形になります：
(, ) からなる文字列が与えられる．部分文字列であって対応のとれたカッコ列であるものについて，長さと出現回数の積の最大値を求めよ．
部分文字列の occurrence の問題なので，suffix tree をとります．suffix tree とは，すべての suffix に対する trie で，適切にノードをまとめることで $O(|S|)$ 頂点の木構造になります．どのような実装が競技プログラミングで広く使われているのかを私は知らないのですが，私は suffix array を経由する次のような理解・実装をしています．
部分文字列というのは suffix の prefix なので，suffix tree からその種類数や出現回数が読み取れます．
suffix tree の各ノードに対して答を計算することにします．出現回数は定数になるので，長さを最大化すればよいです．結局次が解ければよいです：
$a,b,c$ が与えられる．$S[a]$ からはじまる substring $S[a,a+1,…]$ であって対応のとれたカッコ列になるものであって，長さが $b$ 以上 $c$ 以下であるもののうち，最大長を求めよ．
これは $O(\log S)$ 時間で解けます．
例えば，累積和が非負になるような最大長を求め，その後その長さまでの範囲で累積和がちょうど $0$ になるところをとってくるといった要領で実装できます．
