Problem5912--NOI2011湖北省选 一试 第4题 括号修复

5912: NOI2011湖北省选 一试 第4题 括号修复

[Creator : ]
Time Limit : 4.000 sec  Memory Limit : 512 MB

Submit

Description

一个合法的括号序列是这样定义的:
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的‘(’变成‘)’。

Input

第一行是用空格隔开的两个正整数N和M,分别表示字符串的长度和将执行的操作个数。第二行是长度为N的初始字符串S。接下来的M行是将依次执行的M个操作,其中操作名与操作数之间以及相邻操作数之间均用空格隔开。30%的数据满足N,M≤3000。100%的数据满足N,M≤100000。

Output

包含T行,其中T是输入的将执行的M个操作中Query操作出现的次数。Query操作的每次出现依次对应输出文件中的一行,该行只有一个非负整数,表示执行对应Query操作的结果,即:所指字符串至少要改变多少位才能变成合法的括号序列。输入数据保证问题有解。

Sample Input Copy

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

Sample Output Copy

1
2

Source/Category