83410 - 括号修复

时间限制 1 秒 内存限制 128 MB

题目描述

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

现在给你一个长度为 $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
2

输入中有 $2$ 个 Query 操作，所以输出有 $2$ 行。
执行第一个 Query 操作时的括号序列为 ))((，因改变第 $1$ 位可使 $[1,2]$ 之间的字符串变成合法的括号序列，故输出的第一行为 1。

执行第二个 Query 操作时的括号序列为 )(()，因要改变第 $1$ 位和第 $2$ 位才能使 $[1,4]$ 之间的字符串变成合法的括号序列，故输出的第二行为 2。

对于 $100\%$ 的数据， $1\le n,q \le 10^5$ 。

省选