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

样例输出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

1300

难度

分类

(无)

标签

2021小兰赛

递交数

已通过

通过率

被复制

上传者

Takagi-san (njnu19200437)

在下列比赛中:

2021年互联网创新创业科技节程序设计大赛

I. RBS Checking

I. RBS Checking

I. RBS Checking

题目背景

题目描述

输入格式

输出格式

样例输入1

样例输出1

样例1解释

样例输入2

样例输出2

样例输入3

样例输出3

数据范围及限制

信息

相关

状态

开发

支持

I. RBS Checking

I. RBS Checking

I. RBS Checking

题目背景

题目描述

输入格式

输出格式

样例输入1

样例输出1

样例1解释

样例输入2

样例输出2

样例输入3

样例输出3

数据范围及限制

信息

相关

状态

开发

支持

还没有账户？

登录