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

传统题
4.000s 时间限制
512MB 内存限制
11 提交
2 解决
【题目描述】
一个合法的括号序列是这样定义的：
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个操作，其中操作名与操作数之间以及相邻操作数之间均用空格隔开。30%的数据满足N,M≤3000。100%的数据满足N,M≤100000。
【输出】
包含T行，其中T是输入的将执行的M个操作中Query操作出现的次数。Query操作的每次出现依次对应输出文件中的一行，该行只有一个非负整数，表示执行对应Query操作的结果，即：所指字符串至少要改变多少位才能变成合法的括号序列。输入数据保证问题有解。
【样例输入】复制
4 5
((((
Replace 1 2 )
Query 1 2
Swap 2 3
Invert 3 4
Query 1 4
【样例输出】 复制
1
2

题目类型~

竞赛-省选-2011 

咻咻~

提交答案 状态