Cats on the Upgrade (hard version)
Contest: Codeforces Round 765 (Div. 2)
Difficulty rating: 2800
Tags: binary search, data structures, dfs and similar, graphs, trees

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 < 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 < 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 < 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.

Input format:
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 < r \le n$$$), the queries you need to answer. It is guaranteed that all the queries are valid and correspond to the problem statements.

Output format:
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.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Note:
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]$$$.

Example input:
9 8
)(()())()
2 3 6
2 2 7
1 3 4
2 2 7
2 2 9
1 5 6
1 2 7
2 8 9

Example output:
3
4
2
4
1

Editorial:
Now, we need to see how to handle removal queries in this task. Build an SQRT decomposition in the following way. We will rebuild the entire tree after each $$$\sqrt{n}$$$ queries and recalculate the DP. Between the rebuilds, we hold a list of removed leaves.
Now look how we can recalculate the answer if some leaves are removed.
First suppose that the leaf is not a direct child of the vertex we are interested in. Then the removal of this leaf decreases the answer by $$$q$$$, where $$$q$$$ is the number of children of this leaf's parent. Why so? The parent of this leaf had the answer as sum of answers in its children plus $$$\frac{q \cdot (q + 1)}{2}$$$. The answer in the leaf is equal to zero, so the new answer became sum plus $$$\frac{q \cdot (q + 1)}{2}$$$, thus decreased by $$$q$$$.
When we build the DP, the modification of answer in a vertex is passed to its parents unchanged. So, the answer decreases by $$$q$$$ on the entire path from this leaf to the root.
We can easily check if we are affected by this removal. It must be applied only if the removed leaf lies strictly inside our query of the second type.
We also need to handle the case where our leaf is a direct child of the vertex we consider, as the removal described above doesn't fully apply to this case. This is an exercise left to the reader.
So, we get the solution in $$$O((n + q) \cdot \sqrt{n})$$$.
There is also a solution in $$$O((n + q) \log n)$$$. We consider it very shortly.
Let's hold just $$$\frac{k \cdot (k + 1)}{2}$$$ in each vertex, not the sum over children plus $$$\frac{k \cdot (k + 1)}{2}$$$, as we did before. Then the answer for each vertex is the sum in the subtree.
We can keep a Fenwick tree, as we can calculate sums in the subtree with it, using Eulerian tour over the tree. It's not hard to see that each update must be applied only once to the direct parent.