CF380C Sereja and Brackets

Sereja 有一个括号序列 $s_{1},s_{2},...,s_{n}$，换句话说，就是一个长度为 $n$ 的字符串 $s$，只包含字符“(”和“)”。 Sereja 需要回答 $m$ 个询问，每个询问用两个整数 $l_{i},r_{i}$ $(1 \leq l_{i} \leq r_{i} \leq n)$ 描述。第 $i$ 个询问的答案是序列 $s_{l_{i}},s_{l_{i}+1},...,s_{r_{i}}$ 中，最大合法括号子序列的长度。请你帮助 Sereja 回答所有的询问。 你可以在“提示”部分找到对子序列和合法括号序列的定义。

第一行为一个长度为 $n$ 的字符串 $s_{1},s_{2},...,s_{n}$，$(1 \leq n \leq 10^{6})$，字符串中不包含空格。每个字符只可能是“(”或“)”。 第二行为一个整数 $m$ $(1 \leq m \leq 10^5)$，表示询问的个数。 接下来的 $m$ 行，每行两个整数，第 $i$ 行为 $l_{i}, r_{i}$ $(1 \leq l_{i} \leq r_{i} \leq n)$，表示第 $i$ 个询问。

对于每个询问，输出答案，每个答案占一行。按照输入顺序输出。

长度为 $|x|$ 的字符串 $s = s_{1}s_{2}\dots s_{|s|}$ 的子序列是指字符串 $x = s_{k_1}s_{k_2}\dots s_{k_{|x|}}$，其中 $1 \leq k_1 < k_2 < \dots < k_{|x|} \leq |s|$。 一个合法的括号序列是指，可以通过在字符串的字符之间插入字符“1”和“+”后，转化为一个合法的算术表达式的括号序列。例如，括号序列“()()”、“(())”是合法的（分别对应的表达式为“(1)+(1)”、“((1+1)+1)”），而“)(”和“(”都不是合法的。 对于第三个询问，所需的括号序列为“()”。 对于第四个询问，所需的括号序列为“()(())(())”。 由 ChatGPT 5 翻译