翻转括号序列
给定一个长度为 n 的括号序列,要求支持两种操作:
输入的第一行包含两个整数 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。