AT_utpc2025_f.Finite Bracket Sequence

本题的设置与 G 问题相同。

给定一个长度为 $N$ 仅由 ( 和 ) 组成的字符串 $S$。

请你回答 $Q$ 个询问。在第 $i$ 个询问中，给定整数 $L_i, R_i$，请解决如下问题。

考虑字符串 $S$ 的第 $L_i$ 个字符到第 $R_i$ 个字符组成的子串 $X$。

选择一个正整数 $k$，然后从将 $X$ 连续连接 $k$ 次所得到的字符串中，选取其某个子串 $Y$。这里，要求 $Y$ 必须是一个合法的括号序列。$Y$ 可以是空字符串。

请判定 $Y$ 的长度可能的最大值是否存在。

一个合法的括号序列是指，可以通过零次或多次删除形如 () 的子串，最终变为空字符串的字符串。

输入包含如下内容，通过标准输入给出。

$N$ $Q$ $S$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_Q$ $R_Q$

请输出 $Q$ 行。第 $i$ 行对于第 $i$ 个询问，如果 $Y$ 的长度可能的最大值存在，则输出 Finite，否则输出 Infinite。

样例解释 1

第 $1$ 个询问中，$X = $ )(。对于任意正整数 $k$，从将 $X$ 连续连接 $k$ 次所得到的字符串中，删除第一个和最后一个字符得到的长度为 $2k-2$ 的字符串总是合法的括号序列，因此 $Y$ 的长度可能的最大值不存在。所以输出 Infinite。

第 $2$ 个询问中，$X = $ ()((。可以证明 $Y$ 的长度可能的最大值为 $2$，因此输出 Finite。

第 $3$ 个询问中，$X = $ ((。由于 $Y$ 可以为空字符串，所以长度最大值为 $0$，输出 Finite。

数据范围

• $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$

由 ChatGPT 5 翻译