Loading [MathJax]/jax/output/HTML-CSS/jax.js
编程题
                翻转括号序列

题目描述

给定一个长度为 n 的括号序列,要求支持两种操作:

  1. [Li,Ri] 区间内(序列中的第 Li 个字符到第 Ri 个字符)的括号全部翻转(左括号变成右括号,右括号变成左括号)。
  2. 求出以 Li 为左端点时,最长的合法括号序列对应的 Ri(即找出最大的Ri 使 [Li,Ri] 是一个合法括号序列)。

输入描述

输入的第一行包含两个整数 n,m,分别表示括号序列长度和操作次数。

第二行包含给定的括号序列,括号序列中只包含左括号和右括号。

接下来 m 行,每行描述一个操作。如果该行为 “1 Li Ri”,表示第一种操作,区间为 [Li,Ri];如果该行为 “2 Li” 表示第二种操作,左端点为 Li

输出描述

对于每个第二种操作,输出一行,表示对应的 Ri。如果不存在这样的 Ri,请输出 0

输入输出样例

示例

>输入

7 5
((())()
2 3
2 2
1 3 5
2 3
2 1

>输出

4
7
0
0

评测用例规模与约定

对于 20% 的评测用例,n,m5000

对于 40% 的评测用例,n,m30000

对于 60% 的评测用例,n,m100000

对于所有评测用例,1n106,1m2×105

查看答案
赣ICP备20007335号-2