括号序列

题目描述:

JSOI 教练组按如下规则定义配对的括号序列：
1. ( )是配对的括号序列。
2. 若 A 是配对的括号序列，则(A)也是配对的括号序列。
3. 若 A、B 是配对的括号序列，则 AB 也是配对的括号序列。
例如，以下是配对的括号序列：
(())()()((()()))、 ((((()))))、 ()()()()(())
以下则是不配对的括号序列：
)()()()()()(、 (())(()、 (())(()))()(()
繁多的括号总是让 JSOI 教练组看花眼，难以分辨一个很长的括号序列究竟是不是配对的，所
以他请你编写一个程序，输入一个括号序列，并能够完成以下三种操作：
1. 询问将 A[x], A[x+1], … A[y]形成的括号序列修改为配对的括号序列，至少需要修改多少个括
号。
2. 将 A[x], A[x + 1], … A[y]的子序列执行反转，所有的“(”修改为“)”、所有的“)”修改为“(”。
3. 将 A[x], A[x + 1], … A[y]的子序列执行翻转，原子序列被 A[y], A[y – 1], … A[x]替代。

输入格式:

输入数据的第一行包含两个整数 N 和 Q，分别表示括号序列的长度，以及操作的个数。
第二行包含一个长度为 N 的括号序列。
接下来 Q 行，每行三个整数 t、x 和 y，分别表示操作的类型、操作的开始位置和操作的结
束位置，输入数据保证 x 不小于 y。其中 t=0 表示询问操作、t=1 表示反转操作、t=2 表示翻转操
作。

输出格式:

对于每一个询问操作，输出一行，表示将括号序列的该子序列修改为配对，所需的最少改动个数。

样例输入:

6 3
)(())(
0 1 6
0 1 4
0 3 4

样例输出:

2
2
0

提示:

100%的数据满足 N,Q 不超过 10⁵。

时间限制: 2000ms
空间限制: 256MB

---