← 返回题目列表

Codeforces · 1625/E1

E1. 升级中的猫(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。简单版本和困难版本之间的唯一区别是删除查询,它们仅存在于困难版本中。

“星际软件公司”与“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]$$$。