#2329. [HNOI2011] 括号修复

[HNOI2011] 括号修复

题目描述

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

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

现在给你一个长度为 nn 的由 () 组成的字符串,位置标号从 11nn。对这个字符串有下列四种操作:

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

输入格式

输入文件的第一行是用空格隔开的两个正整数 n,qn,q,分别表示字符串的长度和将执行的操作个数。

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

输出格式

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

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

样例说明 1

输入中有 22Query 操作,所以输出有 22 行。

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

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

数据规模与约定

对于 30%30\% 的数据,1n,q30001\le n,q \le 3000
对于 100%100\% 的数据,1n,q1051\le n,q \le 10^5

提示

没有写明提示

题目来源

没有写明来源(题面来自洛谷)