( と ) の個数が等しい場合、またそのときのみ最大値が存在するのは F 問題と同様です。全体を reverse して 2 回解くことで、\(X\) に ( のほうが多いクエリのみ処理できればよいです。

\(S\) に対し ( は \(1\)、) は \(-1\) と置き換えた列の累積和 \((A_0, A_1, \dots, A_N)\) を前計算しておきます。さらに \(d := A_N\) とおきます。以下添字は 0-indexed とします。\(L_i\) を \(L_i-1\) で置き換え、\(X = S[L_i,R_i)\) となるようにします。\(X\) を \(k\) 回連結した文字列を \(X^k\) と表します。

観察: \(Y\) がある \(k\) に関し \(X^k\) の部分文字列であるような正しい括弧列であるが、\(Y\) が \(X\) の部分文字列ではない場合、ある \(L_i \leq l \leq r \leq R_i\) が存在し \(Y = S[r,R_i)+S[L_i,l)\) となる。

\(Y\) が \(X\) に含まれる場合と含まれない場合それぞれについて、\(Y\) の長さの最大値を求めます。

\(Y\) が \(X\) に含まれる場合

分割統治法により，\(0 \leq L_i \leq m \leq R_i \leq N\) (\(m := \lfloor N/2 \rfloor\)) を満たすクエリに対して答えられればよいです。\(Y\) が \(S[L_i,m)\) に含まれる場合、\(S[m,R_i)\) に含まれる場合、どちらでもない場合それぞれについて \(Y\) の長さの最大値を求めます。

\(Y\) が \(S[L_i,m)\) に含まれる場合については，\(S[0,m)\) の各 suffix について部分文字列として含まれる括弧列の長さの最大値を求めればよいです。これは \(O(N)\) で求めることができます。\(Y\) が \(S[m,R_i)\) に含まれる場合も同様です。

\(Y\) が \(S[L_i,m)\) にも \(S[m,R_i)\) にも含まれない場合を考えます。\(Y = S[l,r)\) とおくと，\(L_i \leq l < m < r \leq R_i, A_l = \min\{A_l,A_{l+1},\dots,A_m\} = A_r = \min\{A_m,A_{m+1},\dots,A_r\}\) を満たす \((l,r)\) に関する \(r - l\) の最大値を求めればよいです。\(t := A_m - A_l = A_m - A_r\) を固定すると、\(l\) は \(A_{l'} = \min\{A_{l'},A_{l'+1},\dots,A_m\}\) なる \(l'\) のうち \(L_i\) 以上で \(A_{l'} = A_m-t\) となる最小のもの、\(r\) は \(A_{r'} = \min\{A_m,A_{m+1},\dots,A_{r'}\}\) となる \(r'\) のうち \(R_i\) 以下で \(A_{r'} = A_m-t\) となる最大のものをとればよく、どちらか一方以上が存在しない場合はその \(t\) を実現する \((l,r)\) は存在しません。このときある \(T\) が存在し \(t\) の取りうる範囲は \(0 \leq t \leq T\) となり、この範囲で \(r - l\) は \(t\) について単調に増加します。よって，二分探索により \(T\) を特定した後、再び二分探索により最適な \(l, r\) を求めればよいです。これはクエリの個数 \(q\) について \(O(N+q \log N)\) で行うことができます。

\(Y\) が \(X\) に含まれない場合

\(L_i \leq l \leq r \leq R_i, A_l = \min\{A_{L_i}, A_{L_i+1}, \dots, A_l\}, A_r = \min\{A_r, A_{r+1}, \dots, A_{R_i}\}, A_{R_i}-A_r=A_{L_i}-A_l\) を満たす \((l,r)\) に関する \(r-l\) の最小値を求めればよいです。

非負整数 \(t\) について、\(L^{(t)} := \{l \mid L_i \leq l \leq R_i, A_l = \min\{A_{L_i}, A_{L_i+1},\dots,A_l\} = A_{L_i}-t \}, R^{(t)} := \{r \mid L_i \leq r \leq R_i, A_r = \min\{A_r,A_{r+1},\dots,A_{R_i}\} = A_{R_i}-t\}\) とおきます。\(L^{(t)}, R^{(t)}\) がともに空でないとき、\(\max L^{(t)} < \min R^{(t)}\) となります。実際、そうでないとすると \(A_{R_i}-t = A_{\min R^{(t)}} = \min\{A_{\min R^{(t)}}, A_{\min R^{(t)}+1}, \dots, A_{R_i}\} \leq A_{\max L^{(t)}} = A_{L_i}-t\) となり、これは \(A_{L_i} \leq A_{R_i}\) に矛盾します。よって、\(l \in L^{(t)}, r \in R^{(t)}\) のもとでの \(r-l\) の最小値を与える \((l, r)\) は、\((l,r) = (\max L^{(t)} , \min R^{(t)})\) となります。

次に、\(L^{(t)}, R^{(t)}\) がともに空でないような \(t\) の範囲はある \(T\) により \(0 \leq t \leq T\) と表され、この範囲で \(r-l\) は \(t\) について単調に減少します。よって \(t\) として \(T\) を取り，\((l,r)\) として \((\max L^{(T)}, \min R^{(T)})\) を取るのが最適となります。

各クエリでの \(T\) および \((l,r)\) を特定するため、並列二分探索を行います。\(L^{(t)}\) については，クエリを \(L\) の降順に見ていき、「\(L_i \leq l \leq R_i, A_l = \min\{A_{L_i}, A_{L_i+1},\dots,A_l\} = A_{L_i}-t\) となる \(l\) が存在するかと、存在するならばそのような \(l\) の最小値は何か」というクエリを処理することになります。\(L\) を減らしていき、\(A_l = \min\{A_L, A_{L+1}, \dots, A_l\}\) となるような \(l\) を並べた列を stack で管理します。この列の中では \(A_l\) は単調なので、二分探索により \(l\) の存在とその最小値を求めることができます。同様に \(R^{(t)}\) についてはクエリを \(R\) の昇順に見ていくことになります。この部分の計算量は \(O(N \log N + Q \log^2 N)\) となります。

全体の計算量は \(O(N \log N + Q \log^2 N)\) となります。