P3215 [HNOI2011]括号修复 / [JSOI2011]括号序列

    • 123通过
    • 466提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 Splay 字符串 2011 湖南 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    1. 空串是合法的。
    2. 如果字符串 S 是合法的,则(S)也是合法的。
    3. 如果字符串 AB 是合法的,则 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$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。