A41803. 试题 J: 翻转括号序列问题描述给定一个长度为 n 的括号序列，要求支持两种操作：1. 将 [Li, Ri] 区间内（序列中的第 Li 个字符到第 Ri 个字符）的括号全部翻转（左括号变成右括号，右括号变成左括号）。2. 求出以 Li 为左端点时，最长的合法括号序列对应的 Ri （即找出最大的Ri 使 [Li, Ri] 是一个合法括号序列）。
填空题
困难
知识点
题目描述
试题 J: 翻转括号序列
问题描述
给定一个长度为 n 的括号序列，要求支持两种操作：
1. 将 [Li, Ri] 区间内（序列中的第 Li 个字符到第 Ri 个字符）的括号全部翻转（左括号变成右括号，右括号变成左括号）。
2. 求出以 Li 为左端点时，最长的合法括号序列对应的 Ri （即找出最大的Ri 使 [Li, Ri] 是一个合法括号序列）。
输入格式
输入的第一行包含两个整数 n, m，分别表示括号序列长度和操作次数。第二行包含给定的括号序列，括号序列中只包含左括号和右括号。接下来 m 行，每行描述一个操作。如果该行为 “1 Li Ri”，表示第一种操作，区间为 [Li, Ri] ；如果该行为 “2 Li” 表示第二种操作，左端点为 Li。
输出格式
对于每个第二种操作，输出一行，表示对应的 Ri。如果不存在这样的 Ri，请输出 0。
样例输入
7 5
((())()
2 3
2 2
1 3 5
2 3
2 1
样例输出
4
7
0
0
参考答案
#include <bits/stdc++.h>
using namespace std;
int n, m;
string s;
int op, l, r;
int main() {
scanf("%d%d", &n, &m);
cin >> s;
s = " " + s;
for (int i = 0; i < m; ++i) {
scanf("%d", &op);
if (op == 1) {
scanf("%d%d", &l, &r);
for (int i = l; i <= r; ++i) {
if (s[i] == '(')
s[i] = ')';
else
s[i] = '(';
}
} else {
scanf("%d", &l);
int cur = 0;
r = 0;
for (int i = l; i <= n; ++i) {
if (s[i] == '(')
++cur;
else
--cur;
if (cur == 0) r = i;
if (cur < 0) break;
}
printf("%d\n", r);
}
}
return 0;
}
上一题
下一题