問題一覧 > 通常問題

No.1778 括弧列クエリ / Bracketed Sequence Query

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 53
作問者 : 👑 nullnull / テスター : CuriousFairy315CuriousFairy315
8 ProblemId : 4516 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-25 23:42:24

問題文

整合性の取れた括弧列を、ある文字列であって、連続部分文字列 () を選び、それを削除することを $0$ 回以上繰り返して空文字列が得られるものとします。 また、この操作において一回の操作で消される二文字を、互いと整合をとる文字とします。

括弧列 $S$ の $a$ 文字目を $S_a$ とし、$S_a$ と整合を取る文字を $\overline{S_a}$ とします。$\overline{S_a} = S_b$ であるとき $\overline{a} = b$ とします。

例えば、$(())()$ の場合、これは整合が取れていて、例えば $\overline{S_1} = S_4$ です。

整合性の取れた長さ $N$ の括弧列 $S$ が与えられます。

$i(1 \le i \le Q)$ 番目のクエリでは、$S_{x_i}, \overline{S_{x_i}}, S_{y_i}, \overline{S_{y_i}}$ を内部に含む整合をとっている文字のうち、最も内側であるものの index を出力してください。 より形式的には、$ans_i \le x_i, \overline{x_i}, y_i, \overline{y_i} \le \overline{ans_i}$ となる最大の $ans_i$ を求めてください。等号も許容されることに注意してください。 存在しない場合は、$-1$ を出力してください。

制約

  • $1 \le N, Q \le 2 \times 10^5$
  • $|S| = N$ (ここで $|S|$ は $S$ の長さ)
  • $S$ は整合性の取れた括弧列
  • $1 \le x_i, y_i \le N$
  • $N, Q, x_i, y_i$ はすべて整数

入力

$N\ Q$
$S$
$x_1\ y_1$
$x_2\ y_2$
$\dots$
$x_Q\ y_Q$

出力

$i$ 番目のクエリに対して、$ans_i$ と $\overline {ans_i}$ を昇順で空白区切りで $1$ 行に出力してください。 存在しないケースには $-1$ を出力してください。 合計 $Q$ 行出力してください。最後に改行してください。

サンプル

サンプル1
入力
10 7
(()(()))()
2 4
2 3
2 5
5 7
1 7
1 8
1 10
出力
1 8
2 3
1 8
4 7
1 8
1 8
-1

$1$ 番目のクエリについて、答えを赤、 $S_{x_1}, \overline{S_{x_1}}, S_{y_1}, \overline{S_{y_1}}$ を青で以下に示します。
$\color{red}{(} \color{blue}{(} \color{blue}{)} \color{blue}{(} \color{black}{()} \color{blue}{)} \color{red}{)} \color{black}{()}$

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。