CF1625E1 Cats on the Upgrade (easy version)

这是该问题的简单版本。简单版与困难版的唯一区别在于删除操作，删除操作仅在困难版中出现。 “Interplanetary Software, Inc.” 联合 “Robots of Cydonia, Ltd.” 开发并发布了机器人猫。这些电子宠物会喵叫、抓老鼠，还能以各种方式娱乐主人。 “Interplanetary Software, Inc.” 的开发者们最近决定为这些机器人发布一次软件更新。更新后，猫咪们必须能够解决括号序列相关的问题。下面描述了其中的一个问题。 首先，我们需要了解一些括号序列理论。考虑只包含字符 “(”、“)”、和 “.” 的字符串。如果一个字符串可以通过若干次操作，每次操作可以移除一个单独的 “.” 字符，或移除一个连续的子串 “()”，最终变为空串，则称该字符串为正规括号序列（RBS）。例如，字符串 “(()(.))” 是一个 RBS，因为它可以通过以下移除操作变为空串： “(()(.))” $\rightarrow$ “(()())” $\rightarrow$ “(())” $\rightarrow$ “()” $\rightarrow$ “” 。我们得到了空串，因此初始字符串是一个 RBS。与此同时，字符串 “)(” 不是 RBS，因为无法对其进行上述移除操作。 如果一个 RBS 非空，且不以 “.” 开头，也不以 “.” 结尾，则称其为简单 RBS。 记字符串 $s$ 的子串为其连续子区间。特别地，$s[l\dots r] = s_l s_{l+1} \dots s_r$，其中 $s_i$ 表示字符串 $s$ 的第 $i$ 个字符。 现在，进入题目本身。给定一个只包含 “(” 和 “)” 的字符串 $s$。你需要回答如下类型的询问。 给定两个下标 $l$ 和 $r$（$1 \le l < r \le n$），并保证子串 $s[l\dots r]$ 是一个简单 RBS。你需要求出 $s[l\dots r]$ 中有多少个子串是简单 RBS。换句话说，求有多少对下标 $i$、$j$ 满足 $l \le i < j \le r$ 且 $s[i\dots j]$ 是简单 RBS。 你是 “Interplanetary Software, Inc.” 的一名员工，你的任务是在更新后教会猫咪们解决上述问题。 注意，在本题版本中，字符串中不会出现 “.” 字符。该字符仅在困难版中出现。

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 3\cdot10^5$，$1 \le q \le 3\cdot10^5$），分别表示字符串的长度和询问的数量。 第二行包含一个长度为 $n$ 的字符串 $s$，仅由 “(” 和 “)” 组成。 接下来的 $q$ 行，每行包含三个整数 $t$、$l$ 和 $r$（$t=2$，$1 \le l < r \le n$），表示一条询问。保证所有询问都是合法的并符合题意。注意，$t$ 在本题中恒为 2，仅为困难版保留。

对于每个询问，输出一个整数，表示该区间内简单 RBS 子串的数量。答案按输入顺序输出，每行一个。

考虑示例测试用例。 第一个询问的答案是 $3$，因为有三个满足条件的子串：$s[3\dots6]$、$s[3\dots4]$ 和 $s[5\dots6]$。 第二个询问的答案是 $4$。满足条件的子串为：$s[3\dots6]$、$s[3\dots4]$、$s[5\dots6]$ 和 $s[2\dots7]$。 第三个询问的答案是 $1$。满足条件的子串为：$s[8\dots9]$。 第四个询问的答案是 $6$。满足条件的子串为：$s[3\dots6]$、$s[3\dots4]$、$s[5\dots6]$、$s[2\dots7]$、$s[8\dots9]$ 和 $s[2\dots9]$。 由 ChatGPT 4.1 翻译