I. RBS Checking

I. RBS Checking

测试数据来自 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分

信息

ID
3041
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者