← 返回题目列表

AtCoder · utpc2025_g

G. 最大括号序列

中文机器翻译题面 查看原题

配点 : 100 点

問題文

本题的设定是 F问题共同的。

( 和 ) 组成的长度 N 的字符串 S 。 对于

Q 询问。i 个查询是一个整数 查找 L_i, R_i ,所以请解决以下问题。 使用

S 可以得到第 L_i 从第一个字符开始 R_i 由第几个字符组成的子字符串 X 。

正整数 k 选择,然后进一步 X 该值应乘以 k 次连接的字符串的子字符串 Y 选择来考虑。这里,Y 需要是正确的括号序列。Y 可以是空字符串。

Y 判断作为长度可能存在的最大值是否存在,如果存在请求出该最大值。

正确的括号序列是 正确的括号序列是,() 指删除部分子字符串的操作, 0 次以上重复该操作后可将字符串变为空字符串。

制約

  • N, Q, L_i, R_i 是一个整数
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • S 是 您也可以写 ( 和 ) 组成的长度 N 的字符串
  • 1 \leq L_i \leq R_i \leq N

入力

输入是按以下格式从标准输入给出的。

N Q
S
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

出力

Q 线输出。i 行中,i 个查询,Y 如果作为长度可能存在的最大值存在,则为该最大值,如果不存在则为 -1 。


入力例 1

4 3
()((
2 3
1 4
3 4

出力例 1

-1
2
0

1 个查询中,X = )( 。任意正整数 k , 您可以获得X 该值应乘以 k 从回连结的字符串中删除第一个和最后一个字符所得到的长度 2k-2 的字符串是正确的括号序列,因此,Y 可能的最大长度不存在。

2 个查询中,X = ()(( 。Y 可能的最大长度 可以证明为 2 。 请注意,

3 个查询中,X = (( 。Y 可能的最大长度 可以证明为 0 。Y 也可以是空字符串。