P3215 [HNOI2011] Bracket Repair / [JSOI2011] Bracket Sequence

A valid parenthesis sequence is defined as follows: 1. The empty string is valid. 2. If string `S` is valid, then `(S)` is also valid. 3. If strings `A` and `B` are valid, then `AB` is also valid. You are given a string of length $n$ consisting of `(` and `)`, with positions numbered from $1$ to $n$. The following four operations are supported on this string: - `Replace a b c`: change all parentheses in $[a, b]$ to $c$. For example, given the original string `))())())(`, after performing `Replace 2 7 (`, it becomes `)(((((()(`. - `Swap a b`: reverse the substring in $[a, b]$. For example, given the original string `))())())(`, after performing `Swap 3 5`, it becomes `))))(())(`. - `Invert a b`: flip `(` to `)` and `)` to `(` within $[a, b]$. For example, given the original string `))())())(`, after performing `Invert 4 8`, it becomes `))((()(((`. - `Query a b`: ask for the minimum number of positions in $[a, b]$ that must be changed to make the substring a valid parenthesis sequence. Changing a position means turning `(` into `)` or `)` into `(`. Note that `Query` does not modify the current sequence. For example, given the original string `))())())(`, the result of `Query 3 6` is $2$, because you need to change position $5$ from `)` to `(` and position $6$ from `(` to `)`.

The first line contains two space-separated positive integers $n, q$, denoting the length of the string and the number of operations, respectively. The second line contains the initial string $S$ of length $n$. The next $q$ lines each describe one operation to be performed in order. The operation name and its parameters are separated by single spaces.

For each `Query` operation, output a single line with one integer representing the answer. The input is guaranteed to be solvable.

Sample Explanation: There are $2$ `Query` operations in the input, so the output has $2$ lines. When executing the first `Query`, the parenthesis sequence is `))((`. By changing position $1$, the substring over $[1, 2]$ becomes a valid parenthesis sequence, so the first output line is `1`. When executing the second `Query`, the parenthesis sequence is `)(()`. You need to change position $1$ and position $2$ to make the substring over $[1, 4]$ a valid parenthesis sequence, so the second output line is `2`. Constraints: For $30\%$ of the points, $1 \le n, q \le 3000$. For $100\%$ of the points, $1 \le n, q \le 10^5$. Translated by ChatGPT 5