407749: GYM102889 J 括号序列
Memory Limit:512 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
J. 括号序列time limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output
合法的括号序列定义如下:
- "()" 是一个合法的括号序列。
- 若 "A" 是一个合法的括号序列,则 "(A)" 也是一个合法的括号序列。
- 若 "A", "B" 是一个合法的括号序列,则 "AB" 也是一个合法的括号序列。
- 比如,"((())())" 是一个合法的括号序列,")()(" 不是一个合法的括号序列。
现给出一个长度为 n 的合法的括号序列 S,以及 m 个区间括号变更操作。
区间 l, r 的括号变更操作,会将当前维护的括号序列中,第 l 到 r 个括号进行修改,将这一段中的左括号 "(" 更改为右括号 ")",同时右括号 ")" 更改为左括号 "("。
操作以最初给定的括号序列作为当前维护的括号开始进行,按顺序对当前维护的括号序列进行修改。
请在每次操作之后,判断修改后的序列是否是合法的括号序列。
Input第一行,两个整数 n, m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105),保证 n 为偶数,分别表示括号序列的长度和操作的数量。
第二行,一个长度为 n 的合法的括号序列 S。
接下来 m 行,每行两个整数 lj, rj (1 ≤ lj ≤ rj ≤ n),其中的第 j 行表示第 j 次操作的参数,进行题目所描述的操作。
Output输出 m 行,每行为字符串 yes 或 no,大小写不敏感。
若第 j 个输出为 yes,则表示按顺序进行完第 j 个操作后,括号序列合法;若第 j 个输出为 no,则表示按顺序进行完第 j 个操作后,括号序列不合法。
ExamplesInput4 8 (()) 2 3 2 3 2 4 2 2 3 4 1 2 3 4 1 4Output
yeS YeS no no yEs no NO yeSInput
8 12 ((()())) 4 5 6 7 1 6 2 7 1 2 4 7 5 8 2 6 1 5 1 2 7 8 2 8Output
yeS No no no yEs yes NO NO No nO YeS NoNote
在第一个样例中,操作后的括号序列如下表: