这是问题的简单版本。简单版本和困难版本之间的唯一区别是删除查询,它们仅存在于困难版本中。
“星际软件公司”与“Cydonia 机器人有限公司”一起开发并发布了机器猫。这些电子宠物可以喵喵叫、抓老鼠,并以各种方式娱乐主人。
来自“Interplanetary Software, Inc.”的开发人员最近决定为这些机器人发布软件更新。更新后,猫们必须解决括号序列的问题。下面描述问题之一。
首先,我们需要学习一些括号序列理论。考虑包含字符“(”、“)”和“.”的字符串。如果可以通过删除单个“.”的一个或多个操作将字符串转换为空字符串,则将该字符串称为常规括号序列 (RBS)。字符,或连续子串“()”。例如,字符串“(()(.))”是一个 RBS,因为它可以通过以下删除序列转换为空字符串:
“(()(.))”$$$\rightarrow$$$“(()())”$$$\rightarrow$$$“(())”$$$\rightarrow$$$“()”$$$\rightarrow$$$“”。
我们得到一个空字符串,因此初始字符串是 RBS。同时,字符串“)(”不是 RBS,因为不可能对其应用此类删除操作。
如果 RBS 不为空、不以“.”开头且不以“.”结尾,则该 RBS 很简单。
将字符串 $$$s$$$ 的子字符串表示为其连续子段。特别是,$$$s[l\dots r] = s_ls_{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$$$)、字符串长度和查询次数。
第二行包含字符串$$$s$$$,由$$$n$$$字符“(”和“)”组成。
以下 $$$q$$$ 行中的每一行都包含三个整数 $$$t$$$、$$$l$$$ 和 $$$r$$$ ($$$t = 2$$$, $$$1 \le l < r \le n$$$),即您需要回答的查询。保证所有查询都是有效的并且与问题陈述相对应。请注意,$$$t$$$ 未使用,并且在此问题中始终等于 2。这是问题的困难版本所必需的。
输出
对于每个查询,在单独的行中打印一个整数,即简单 RBS 的子字符串的数量。答案必须按照输入中指定的查询的顺序打印。
示例
输入 #1
9 4 )(()())() 2 3 6 2 2 7 2 8 9 2 2 9
输出 #1
3 4 1 6
注意
考虑示例测试用例。
第一个查询的答案是 $$$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]$$$。