蓝桥杯2021国赛AB组：括号序列翻转与最长合法子串查询（线段树+二分）
题目描述
给定长度为 n 的括号序列（仅包含 '(' 和 ')'），支持两种操作：
- 翻转操作：将区间 [Li, Ri] 内所有括号翻转（'(' 变 ')'，')' 变 '('）。
- 查询操作：给定左端点 Li，找到最大的 Ri，使得子串 [Li, Ri] 是一个合法括号序列；若不存在，输出 0。
数据范围
- 1 ≤ n ≤ 106
- 1 ≤ m ≤ 2 × 105
分析思路
将序列映射为数值：'(' = 1，')' = -1。则合法括号序列等价于：区间和为 0，且任意前缀和非负。利用前缀和 pre[i]，合法括号序列 [l, r] 满足：
pre[r] == pre[l-1]
min{pre[k] | k ∈ [l, r]} ≥ pre[l-1]
因此问题转化为：找到最大的 r，使得 pre[r] = pre[l-1] 且区间 [l, r] 内所有 pre 值不小于 pre[l-1]。
操作一：区间翻转
翻转区间 [l, r] 后，前缀和数组的变化规律：
- 区间 [l, r] 内 pre 值变为相反数，并加上 2×pre[l-1]（因为翻转后，区间起点的影响需要修正）。
- 区间 [r+1, n] 内 pre 值减少 2×(翻转后区间最后一个元素的新值)。
为简化实现，可将翻转分解为两次操作：先翻转前缀 [1, r]，再翻转前缀 [1, l-1]。这样只需维护两种懒惰标记：
- 翻转标记 (rev)：交换节点最大值和最小值，并取负。
- 加法标记 (add)：区间整体添加一个常数。
两种标记需要正确处理相互影响：当节点被翻转时，加法标记也应取负。
操作二：查询
朴素二分法：对每个查询，二分右端点位置，用线段树查询区间最小值。复杂度 O(m log² n)，数据较大时需优化。
优化方法：在线段树上直接二分，利用前缀和的连续性——若区间内最小值小于目标值，则第一个小于目标值的点必然在更左侧；若区间内所有值都不小于目标值，则需找到最后一个等于目标值的点。
算法步骤
- 查找第一个小于目标值的位置：若存在，则合法右端点可能在该位置左侧。
- 若不存在小于目标值的位置：则区间内所有 pre 值 ≥ 目标值，需查找最后一个等于目标值的位置。
实现细节
线段树节点属性
mn：区间最小值mx：区间最大值lazy_rev：翻转标记lazy_add：加法标记
关键函数
build：构建线段树push_down：下传懒标记，处理 rev 和 add 的相互作用update_rev：区间翻转update_add：区间加常数query_pos：单点查询query_first_less：寻找第一个小于目标值的位置query_last_equal：寻找最后一个等于目标值的位置
时间复杂度
优化后 O(n log n)，适用于大数据范围。
代码实现 (C++)
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int maxn = 1e6 + 5;
int n, q;
string s;
int pre[maxn];
struct SegTree {
int mn[maxn << 2], mx[maxn << 2];
int lazy_add[maxn << 2];
bool lazy_rev[maxn << 2];
void build(int p, int l, int r) {
if (l == r) {
mn[p] = mx[p] = pre[l];
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
}
void push_down(int p) {
if (lazy_rev[p]) {
swap(mn[p << 1], mx[p << 1]);
mn[p << 1] = -mn[p << 1];
mx[p << 1] = -mx[p << 1];
swap(mn[p << 1 | 1], mx[p << 1 | 1]);
mn[p << 1 | 1] = -mn[p << 1 | 1];
mx[p << 1 | 1] = -mx[p << 1 | 1];
lazy_rev[p << 1] ^= 1;
lazy_rev[p << 1 | 1] ^= 1;
lazy_add[p << 1] *= -1;
lazy_add[p << 1 | 1] *= -1;
lazy_rev[p] = 0;
}
if (lazy_add[p]) {
mx[p << 1] += lazy_add[p];
mn[p << 1] += lazy_add[p];
mx[p << 1 | 1] += lazy_add[p];
mn[p << 1 | 1] += lazy_add[p];
lazy_add[p << 1] += lazy_add[p];
lazy_add[p << 1 | 1] += lazy_add[p];
lazy_add[p] = 0;
}
}
void update_rev(int p, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
swap(mn[p], mx[p]);
mn[p] = -mn[p];
mx[p] = -mx[p];
lazy_rev[p] ^= 1;
lazy_add[p] *= -1;
return;
}
push_down(p);
int mid = (l + r) >> 1;
if (ql <= mid) update_rev(p << 1, l, mid, ql, qr);
if (qr > mid) update_rev(p << 1 | 1, mid + 1, r, ql, qr);
mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
}
void update_add(int p, int l, int r, int ql, int qr, int val) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
mn[p] += val;
mx[p] += val;
lazy_add[p] += val;
return;
}
push_down(p);
int mid = (l + r) >> 1;
if (ql <= mid) update_add(p << 1, l, mid, ql, qr, val);
if (qr > mid) update_add(p << 1 | 1, mid + 1, r, ql, qr, val);
mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
}
int query_pos(int p, int l, int r, int pos) {
if (pos < 1) return 0;
if (l == r) return mn[p];
push_down(p);
int mid = (l + r) >> 1;
if (pos <= mid) return query_pos(p << 1, l, mid, pos);
else return query_pos(p << 1 | 1, mid + 1, r, pos);
}
int first_less(int p, int l, int r, int pos, int val) {
if (l == r) return l;
push_down(p);
int mid = (l + r) >> 1;
int ans = 0;
if (pos <= mid && mn[p << 1] < val)
ans = first_less(p << 1, l, mid, pos, val);
if (ans) return ans;
if (mn[p << 1 | 1] < val)
ans = first_less(p << 1 | 1, mid + 1, r, pos, val);
return ans;
}
int last_equal(int p, int l, int r, int pos, int val) {
if (l == r) return l;
push_down(p);
int mid = (l + r) >> 1;
int ans = 0;
if (mn[p << 1 | 1] <= val)
ans = last_equal(p << 1 | 1, mid + 1, r, pos, val);
if (ans) return ans;
if (pos <= mid && mn[p << 1] <= val)
ans = last_equal(p << 1, l, mid, pos, val);
return ans;
}
} seg;
void solve() {
cin >> n >> q >> s;
for (int i = 1; i <= n; ++i) {
pre[i] = (s[i-1] == '(' ? 1 : -1);
pre[i] += pre[i-1];
}
seg.build(1, 1, n);
while (q--) {
int op, l, r;
cin >> op;
if (op == 1) {
cin >> l >> r;
int v1 = seg.query_pos(1, 1, n, l-1);
seg.update_rev(1, 1, n, 1, l-1);
seg.update_add(1, 1, n, l, n, -2*v1);
int v2 = seg.query_pos(1, 1, n, r);
seg.update_rev(1, 1, n, 1, r);
seg.update_add(1, 1, n, r+1, n, -2*v2);
}
else {
cin >> l;
int val = seg.query_pos(1, 1, n, l-1);
int pos = seg.first_less(1, 1, n, l, val);
if (pos) {
if (pos-1 >= l) cout << pos-1 << "\n";
else cout << 0 << "\n";
}
else {
pos = seg.last_equal(1, 1, n, l, val);
cout << (pos ? pos : 0) << "\n";
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
