CF1625E2 Cats on the Upgrade (hard 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_ls_{l+1}\dots s_r$，其中 $s_i$ 表示字符串 $s$ 的第 $i$ 个字符。 现在，正式进入题目部分。给定一个初始只包含 “(” 和 “)” 的字符串 $s$，你需要回答以下两种操作： 1. 给定两个下标 $l$ 和 $r$（$1 \le l < r \le n$）。保证第 $l$ 个字符为 “(”，第 $r$ 个字符为 “)” ，且它们之间的字符全为 “.”。你需要将第 $l$ 和第 $r$ 个字符都改为 “.”。 2. 给定两个下标 $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 \in \{1, 2\}$，$1 \le l < r \le n$），表示一个操作。保证所有操作均合法且符合题意。

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

考虑样例测试。 第一个查询的答案为 $3$，有三个满足条件的子串：$s[3\dots6]$、$s[3\dots4]$ 和 $s[5\dots6]$。 第二个查询的答案为 $4$。这些子串为：$s[3\dots6]$、$s[3\dots4]$、$s[5\dots6]$ 和 $s[2\dots7]$。 第三次操作后，字符串变为 “)(..())()”。 第四个查询的答案为 $2$。这些子串为：$s[5\dots6]$ 和 $s[2\dots7]$。注意 $s[3\dots6]$ 不再是简单 RBS，因为它以 “.” 开头。 第五个查询的答案为 $4$。这些子串为：$s[5\dots6]$、$s[2\dots7]$、$s[8\dots9]$ 和 $s[2\dots9]$。 第六次操作后，字符串变为 “)(....)()”。 第七次操作后，字符串变为 “)......()”。 第八个查询的答案为 $1$。该子串为 $s[8\dots9]$。 由 ChatGPT 4.1 翻译