Comet OJ

C1128 [HNOI2011]括号修复

内存限制：256 MB 时间限制：1000 ms

题目描述

一个合法的括号序列是这样定义的：

  1. 空串是合法的。
  2. 如果字符串S是合法的，则(S)也是合法的。
  3. 如果字符串A和B是合法的，则AB也是合法的。

现在给你一个长度为 $N$ 的由(和)组成的字符串，位置标号从 $1$ 到 $N$。对这个字符串有下列四种操作：

  1. Replace a b c：将 $[a,b]$ 之间的所有括号改成 $c$。例如：假设原来的字符串为：))())())(，那么执行操作Replace 2 7后原来的字符串变为：)(((((()(。
  2. Swap a b：将 $[a,b]$ 之间的字符串翻转。例如：假设原来的字符串为：))())())(，那么执行操作Swap 3 5后原来的字符串变为：))))(())(。
  3. Invert a b：将 $[a,b]$ 之间的(变成),)变成(。例如：假设原来的字符串为：))())())(，那么执行操作Invert 4 8后原来的字符串变为：))((()(((。
  4. Query a b：询问 $[a,b]$ 之间的字符串至少要改变多少位才能变成合法的括号序列。改变某位是指将该位的(变成)或)变成(。注意执行操作Query并不改变当前的括号序列。例如：假设原来的字符串为：))())())(，那么执行操作Query 3 6的结果为 $2$，因为要将位置 $5$ 的)变成(并将位置 $6$ 的(变成)。

输入格式

第一行是用空格隔开的两个正整数 $N$ 和 $M$，分别表示字符串的长度和将执行的操作个数。

第二行是长度为 $N$ 的初始字符串 $S$。接下来的 $M$ 行是将依次执行的 $M$ 个操作，其中操作名与操作数之间以及相邻操作数之间均用空格隔开。

输出

输出文件包含 $T$ 行，其中 $T$ 是输入的将执行的 $M$ 个操作中Query操作出现的次数。Query操作的每次出现依次对应输出中的一行，该行只有一个非负整数，表示执行对应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\%$ 的数据满足 $N,M≤3000$。

$100\%$ 的数据满足 $N,M≤100000$。