Dotcpp  >  编程题库  >  蓝桥杯2021年第十二届国赛真题-翻转括号序列
题目 2615:

蓝桥杯2021年第十二届国赛真题-翻转括号序列

时间限制: 2s 内存限制: 192MB 提交: 1007 解决: 67

题目描述

给定一个长度为 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, m ≤ 5000;
对于 40% 的评测用例,n, m ≤ 30000;
对于 60% 的评测用例,n, m ≤ 100000;
对于所有评测用例,1 ≤ n ≤ 106, 1 ≤ m ≤ 2 × 105
标签