AT_mujin_pc_2016_d 括弧列

我们偏爱正确的括弧列。正确括弧列的定义如下。 1. 空串是一个正确的括弧列。 2. 若字符串 $s$ 是一个正确的括弧列，则 `(` $+$ $s$ $+$ `)` 也是一个正确的括弧列。 3. 若字符串 $s$ 和 $t$ 都是正确的括弧列，则 $s + t$ 也是一个正确的括弧列。 你有一个长度为 $N$ 的字符串 $S$。$S$ 仅由 `(`、`)` 和 `?` 构成。 你的任务是回答关于字符串 $S$ 的 $Q$ 个询问。第 $i$ 个询问如下： - 设 $S_i$ 为 $S$ 中从第 $l_i$ 个字符到第 $r_i$ 个字符（含两端）的子串。是否有可能通过将每个 `?` 替换为 `(` 或 `)`，使得 $S_i$ 成为一个正确的括弧列？

输入从标准输入按以下格式给出： > $N$ > $S$ > $Q$ > $l_1$ $r_1$ > $l_2$ $r_2$ > $:$ > $l_Q$ $r_Q$ - 第一行为整数 $N$（$1 \le N \le 10^5$），表示字符串 $S$ 的长度。 - 第二行为字符串 $S$。$S$ 仅由 `(`、`)` 和 `?` 组成。 - 第三行为整数 $Q$（$1 \le Q \le 10^5$），表示询问的数量。 - 接下来的 $Q$ 行描述询问。其中第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le N$），以空格分隔。

输出 $Q$ 行。在第 $i$ 行中，根据第 $i$ 个询问的答案，输出 `Yes` 或 `No`。

由 DeepSeek 翻译