测试数据来自 nnu_contest/1300

I. RBS Checking

时间限制:3s

空间限制:64MB

本题分值:600

题目背景

我们这样定义合法括号串：

①（）是合法括号串。

②若\(s\)是合法括号串，则\((s)\)是合法括号串。

③若\(s,t\)是合法括号串，则\(st\)是合法括号串。

例如：(()())是合法括号串， 但)(()不是合法括号串。

题目描述

给定一个由 '(' 和 ')' 构成的括号串 \(s\) 和 \(q\) 次操作。每次操作是以下三种之一：

• 操作1：操作将以 \(1 \ l\ r\) 的形式给出，表示将 \(s[l],s[l+1],...s[r]\) 的括号翻转，即'(' 变为')'，而')'变为'('。

• 操作2：操作将以 \(2\ l\ r\) 的形式给出，询问 \(s[l], s[l+1],...s[r]\) 构成的括号串是否是合法括号串。合法则输出Yes，不合法则输出No（请注意大小写）

• 操作3：操作将以 \(3\ l\ r\) 的形式给出，询问对于括号串 \(s[l],s[l+1],...s[r]\) ，至少需要在其中添加几个括号，才能将其变为合法括号串。注意，只能在任意位置添加括号，而不能改变原先括号的顺序；操作3仅仅是询问，而不会改变这个括号串。

输入格式

第一行包含两个正整数 \(n, q\) ，分别表示字符串长度和操作次数。

第二行包含一个括号串 \(s\) ，字符串中仅包含左括号'('和右括号')'

接下来 \(q\) 行每行三个整数 \(op\ l\ r\) ，分别表示操作类型，操作对应的左右区间。

输出格式

对于第二种和第三种操作，输出询问所对应的答案。每个答案输出一行。

样例输入1

4 5
()()
2 1 2
3 2 3
1 1 2
1 2 4
3 1 3

样例输出1

Yes
2
3

样例1解释

第一次操作，询问1~2的子串是否是合法括号串，子串为()，故回答Yes

第二次操作，询问)(至少需要添加几个括号才能变为合法括号串，答案是2个，变为()()。

执行 1 1 2 后，括号序列变为 )(()

执行 1 2 4 后，括号序列变为 )))(

第五次操作，此时1~3的序列为)))，输出3

样例输入2

97 25
((((()()))()())())))(()()(())((())))))()(()((((())((()))((((()))))((((((()((()((((((((()())((())(
2 2 23
1 44 45
2 54 91
1 36 83
2 50 55
1 12 48
1 11 45
2 74 83
1 74 89
1 37 93
2 50 59
1 56 74
1 23 82
1 1 95
1 41 51
1 18 34
1 76 91
2 16 95
1 2 36
1 52 86
2 5 34
1 64 78
1 1 67
1 15 56
2 9 66

样例输出2

No
No
No
No
No
No
No
Yes

样例输入3

156 87
()()()()()()()))()()()()()()()()()))((((()()()()()((()()()()((()()()()()()()()()))((()()()()()()()()((()()()()()()((()))()()()()()()()()((()((()()()))()()((
3 5 93
2 52 113
2 9 60
2 116 145
3 77 135
1 42 101
2 55 86
1 44 84
3 57 90
3 28 72
1 116 133
2 80 141
2 125 126
1 110 144
3 74 114
2 54 89
1 55 66
1 30 139
2 13 112
3 47 125
3 75 98
2 50 51
1 102 137
1 40 152
3 25 95
3 23 70
3 29 78
2 66 87
1 43 142
1 4 122
2 60 109
3 40 126
3 89 150
1 17 52
2 19 106
2 24 47
2 10 17
2 68 79
3 22 129
3 57 105
1 16 91
2 125 134
3 32 155
1 12 92
1 85 149
3 12 21
2 22 137
1 51 77
3 98 129
3 5 15
3 22 46
3 137 156
1 16 91
3 11 72
3 61 110
1 19 40
1 11 152
1 63 95
1 131 134
1 39 61
2 49 86
1 1 74
1 76 94
3 52 92
3 106 153
1 132 138
1 44 73
3 31 133
2 87 116
1 15 32
3 30 133
3 60 104
2 79 92
3 57 129
2 46 141
2 80 125
3 46 145
1 54 58
2 57 156
2 61 82
3 59 141
2 112 123
1 12 146
3 64 132
2 61 90
3 20 123
2 48 59

样例输出3

13
No
No
No
7
No
2
11
No
No
7
No
No
5
2
Yes
1
2
2
No
No
13
12
No
No
No
No
8
5
No
14
4
No
2
3
7
6
16
10
No
3
4
3
No
4
3
No
5
No
No
6
No
No
5
No
9
No
6
No

数据范围及限制

字符串中仅包含左括号'('和右括号')'。设 \(n\) 是字符串的长度，×表示该操作不会在该测试点中出现。

操作只会以 \(op\ l\ r\) 的形式给出，其中 \(op\in \{1,2,3\},1\le l\le r\le n\)

测试点编号	\(n\)	\(q\)	操作1	操作2	操作3	测试点分值
1~2	\(n=10\)	\(1\le q\le 100\)	×	√	×	每个测试点30分
3~4	\(n=100\)	\(1\le q\le 100\)	√	√	×	每个测试点30分
5~6	\(n=500\)	\(1\le q\le 500\)	√	√	√	每个测试点40分
7~9	\(n=299998\)	\(1\le q\le 3*10^5\)	×	√	×	每个测试点40分
10~12	\(n=299999\)	\(1\le q\le 3*10^5\)	×	√	√	每个测试点40分
13~14	\(n=300000\)	\(1\le q\le 3*10^5\)	√	√	√	每个测试点80分