P10513 Parentheses

Yuan gives you a string $S$ of length $n$. $S$ consists only of ```(``` and ```)```. She will perform $m$ operations on it. There are two types of operations: 1. ```1 l r```: She will flip the parentheses from $l$ to $r$, i.e., ```(``` becomes ```)```, and ```)``` becomes ```(```. 1. ```2 l r```: She wants to know the value of the length of the longest valid parentheses subsequence in the interval $\left[ l,r\right]$, divided by $2$. Yuan considers the following parentheses sequences to be valid: 1. The empty sequence is a valid sequence. 1. If ```A``` is a valid sequence, then ```(A)``` is also a valid sequence. 1. If ```A``` and ```B``` are both valid sequences, then ```AB``` is also a valid sequence. Yuan considers a subsequence of sequence $a$ to be a sequence $[a_{i_1},a_{i_2},...a_{i_k}]$ that satisfies $1\le i_1

The first line contains an integer $n$. The second line contains a string $S$ of length $n$, guaranteed to consist only of ```(``` and ```)```. The third line contains an integer $m$. The next $m$ lines each contain three numbers $op$, $l$, $r$, corresponding to the two operations above.

For each operation with $op=2$, output one line containing an integer, representing the answer.

**[Sample Explanation]** - The first extracted string is ```()```, and the answer is $1$. - After flipping, the string becomes ```))(())```. - The second extracted string is ```)(```, and the answer is $0$. - The third extracted string is ```())```, and the answer is $1$. - The fourth extracted string is ```(())```, and the answer is $2$. **[Constraints]** - For $10\%$ of the testdata, $1 \leq n,m \leq 500$. - For $20\%$ of the testdata, $1 \leq n,m \leq 5000$. - For $40\%$ of the testdata, $1 \leq n,m \leq 2\times 10^5$. - Another $10\%$ of the testdata satisfies $op=2$ and is randomly generated. - Another $15\%$ of the testdata satisfies $op=2$, but the testdata is not guaranteed to be randomly generated. For all testdata, it is guaranteed that $1\le n \le 5\times 10^5$, $1\le m \le 5 \times 10^5$, $1 \le l \le r \le n$, $op \in \{1,2\}$. The testdata has multiple levels. Translated by ChatGPT 5