试题 J: 翻转括号序列

问题描述

给定一个长度为 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