CF1625E2.Cats on the Upgrade (hard version)

This is the hard version of the problem. The only difference between the easy and the hard versions are removal queries, they are present only in the hard version.

"Interplanetary Software, Inc." together with "Robots of Cydonia, Ltd." has developed and released robot cats. These electronic pets can meow, catch mice and entertain the owner in various ways.

The developers from "Interplanetary Software, Inc." have recently decided to release a software update for these robots. After the update, the cats must solve the problems about bracket sequences. One of the problems is described below.

First, we need to learn a bit of bracket sequence theory. Consider the strings that contain characters "(", ")" and ".". Call a string regular bracket sequence (RBS), if it can be transformed to an empty string by one or more operations of removing either single "." characters, or a continuous substring "()". For instance, the string "(()(.))" is an RBS, as it can be transformed to an empty string with the following sequence of removals:

"(()(.))" $\rightarrow$ "(()())" $\rightarrow$ "(())" $\rightarrow$ "()" $\rightarrow$ "".

We got an empty string, so the initial string was an RBS. At the same time, the string ")(" is not an RBS, as it is not possible to apply such removal operations to it.

An RBS is simple if this RBS is not empty, doesn't start with ".", and doesn't end with ".".

Denote the substring of the string $s$ as its sequential subsegment. In particular, $s[l\dots r] = s_ls_{l+1}\dots s_r$, where $s_i$ is the $i$-th character of the string $s$.

Now, move on to the problem statement itself. You are given a string $s$, initially consisting of characters "(" and ")". You need to answer the following queries:

1. Given two indices, $l$ and $r$ ($1 \le l \lt r \le n$). It's guaranteed that the $l$-th character is equal to "(", the $r$-th character is equal to ")", and the characters between them are equal to ".". Then the $l$-th and the $r$-th characters must be set to ".".
2. Given two indices, $l$ and $r$ ($1 \le l \lt r \le n$), and it's guaranteed that the substring $s[l\dots r]$ is a simple RBS. You need to find the number of substrings in $s[l\dots r]$ such that they are simple RBS. In other words, find the number of index pairs $i$, $j$ such that $l \le i \lt j \le r$ and $s[i\dots j]$ is a simple RBS.

You are an employee in "Interplanetary Software, Inc." and you were given the task to teach the cats to solve the problem above, after the update.

这是该问题的困难版本。简单版本与困难版本的唯一区别在于删除操作：仅在困难版本中存在删除查询。

“星际软件公司（Interplanetary Software, Inc.）”联合“赛东尼亚机器人有限公司（Robots of Cydonia, Ltd.）”共同研发并发布了机器人猫。这些电子宠物能够喵喵叫、抓老鼠，并以多种方式为主人提供娱乐。

“星际软件公司”的开发人员最近决定为这些机器人发布一次软件更新。更新后，机器人猫必须能够解决关于括号序列的问题。其中一个具体问题如下所述。

首先，我们需要了解一些括号序列理论。考虑仅由字符 "(", ")" 和 "." 组成的字符串。若一个字符串可通过若干次（至少一次）如下操作变为空字符串，则称其为正则括号序列（Regular Bracket Sequence, RBS）：每次操作可移除单个字符 "."，或移除一个连续子串 "()"。例如，字符串 "(()(.))" 是一个 RBS，因为它可通过如下一系列移除操作变为空字符串：

"(()(.))" $\rightarrow$ "(()())" $\rightarrow$ "(())" $\rightarrow$ "()" $\rightarrow$ ""。

我们最终得到了空字符串，因此初始字符串是一个 RBS。而字符串 ")(" 则不是 RBS，因为无法对它执行上述任何移除操作。

若一个 RBS 非空、不以 "." 开头、也不以 "." 结尾，则称其为简单 RBS（simple RBS）。

记字符串 $s$ 的子串（substring） 为其连续子段。特别地，记 $s[l\dots r] = s_ls_{l+1}\dots s_r$，其中 $s_i$ 表示字符串 $s$ 的第 $i$ 个字符。

现在进入问题本身。给定一个初始仅由字符 "(" 和 ")" 构成的字符串 $s$，你需要回答以下两类查询：

1. 给定两个下标 $l$ 和 $r$（满足 $1 \le l \lt r \le n$）。保证第 $l$ 个字符为 "("，第 $r$ 个字符为 ")"，且二者之间的所有字符均为 "."。此时需将第 $l$ 个和第 $r$ 个字符均修改为 "."。
2. 给定两个下标 $l$ 和 $r$（满足 $1 \le l \lt r \le n$），且保证子串 $s[l\dots r]$ 是一个简单 RBS。你需要计算子串 $s[l\dots r]$ 中有多少个子串本身也是简单 RBS。换言之，求满足 $l \le i \lt j \le r$ 且 $s[i\dots j]$ 是简单 RBS 的下标对 $(i, j)$ 的数量。

你作为“星际软件公司”的一名员工，被委派在本次更新后教会机器人猫解决上述问题。

The first line contains two integers $n$ and $q$ ($2 \le n \le 3\cdot10^5$, $1 \le q \le 3\cdot10^5$), the length of the string, and the number of queries.

The second line contains the string $s$, consisting of $n$ characters "(" and ")".

Each of the following $q$ lines contains three integers $t$, $l$ and $r$ ($t \in {1, 2}$, $1 \le l \lt r \le n$), the queries you need to answer. It is guaranteed that all the queries are valid and correspond to the problem statements.

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 3\cdot10^5$，$1 \le q \le 3\cdot10^5$），分别表示字符串的长度和查询次数。

第二行包含字符串 $s$，由 $n$ 个字符组成，每个字符为 ( 或 )。

接下来的 $q$ 行每行包含三个整数 $t$、$l$ 和 $r$（$t \in \{1, 2\}$，$1 \le l \lt r \le n$），表示需要回答的查询。保证所有查询均合法，且符合题目描述。

For each query, print a single integer in a separate line, the number of substrings that are simple RBS. The answers must be printed in the same order as the queries are specified in the input.

对于每个查询，在单独的一行中输出一个整数，表示是简单 RBS 的子串数量。答案的输出顺序必须与输入中查询的顺序一致。

Consider the example test case.

The answer to the first query is $3$, as there are three suitable substrings: $s[3\dots6]$, $s[3\dots4]$ and $s[5\dots6]$.

The answer to the second query is $4$. The substrings are $s[3\dots6]$, $s[3\dots4]$, $s[5\dots6]$ and $s[2\dots7]$.

After the third query, the string becomes ")(..())()".

The answer to the fourth query is $2$. The substrings are $s[5\dots6]$ and $s[2\dots7]$. Note that $s[3\dots6]$ is not a simple RBS anymore, as it starts with ".".

The answer to the fifth query is $4$. The substrings are $s[5\dots6]$, $s[2\dots7]$, $s[8\dots9]$ and $s[2\dots9]$.

After the sixth query, the string becomes ")(....)()".

After the seventh query, the string becomes ")......()".

The answer to the eighth query is $1$. The substring is $s[8\dots9]$.

考虑示例测试用例。

第一个查询的答案为 $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]$。