[HNOI2011] 括号修复 / [JSOI2011]括号序列

题目描述

一个合法的括号序列是这样定义的: 1. 空串是合法的。 2. 如果字符串 `S` 是合法的,则`(S)`也是合法的。 3. 如果字符串 `A` 和 `B` 是合法的,则 `AB` 也是合法的。 现在给你一个长度为 $n$ 的由`(`和`)`组成的字符串,位置标号从 $1$ 到 $n$。对这个字符串有下列四种操作: - `Replace a b c`:将 $[a,b]$ 之间的所有括号改成 $c$。假设原来的字符串为:`))())())(`,那么执行操作 `Replace 2 7 (` 后原来的字符串变为:`)(((((()(`。 - `Swap a b`:将 $[a,b]$ 之间的字符串翻转。假设原来的字符串为:`))())())(`,那么执行操作 `Swap 3 5` 后原来的字符串变为:`))))(())(`。 - `Invert a b`:将 $[a,b]$ 之间的 `(` 变成 `)` ,`)` 变成 `(`。假设原来的字符串为:`))())())(`,那么执行操作 `Invert 4 8` 后原来的字符串变为:`))((()(((`。 - `Query a b`:询问 $[a,b]$ 之间的字符串至少要改变多少位才能变成合法的括号序列。改变某位是指将该位的 `(` 变成 `)` 或 `)` 变成 `(`。注意执行操作 `Query` 并不改变当前的括号序列。假设原来的字符串为:`))())())(`,那么执行操作 `Query 3 6` 的结果为 $2$,因为要将位置 $5$ 的`)`变成`(`并将位置 $6$ 的`(`变成`)`。

输入输出格式

输入格式


输入文件的第一行是用空格隔开的两个正整数 $n,q$,分别表示字符串的长度和将执行的操作个数。 第二行是长度为 $n$ 的初始字符串 $S$。接下来的 $q$ 行是将依次执行的$q$个操作,其中操作名与操作数之间以及相邻操作数之间均用空格隔开。

输出格式


对于每个 `Query` 操作,输出一行一个整数表示答案。输入数据保证有解。

输入输出样例

输入样例 #1

4 5
((((
Replace 1 2 )
Query 1 2
Swap 2 3
Invert 3 4
Query 1 4

输出样例 #1

1
2

说明

### 样例解释 输入中有 $2$ 个 `Query` 操作,所以输出有 $2$ 行。 执行第一个 `Query` 操作时的括号序列为 `))((`,因改变第 $1$ 位可使 $[1,2]$ 之间的字符串变成合法的括号序列,故输出的第一行为 `1`。 执行第二个 `Query` 操作时的括号序列为 `)(()`,因要改变第 $1$ 位和第 $2$ 位才能使 $[1,4]$ 之间的字符串变成合法的括号序列,故输出的第二行为 `2`。 ### 数据范围 对于 $30\%$ 的数据,$1\le n,q \le 3000$; 对于 $100\%$ 的数据,$1\le n,q \le 10^5$。