算法
(线段树) $O(N\log N)$
我们不妨将 (
视作 +1
,将 )
视作 -1
这样就变成了仅包含 +1
和 -1
序列
考察区间 $[l, r]$ 是否合法,仅需满足以下两个条件即可:
- $S[l \cdots r]$ 的区间和 $s$ 为 $0$
- $S[l \cdots r]$ 的前缀和序列的最小值 $d$ 为 $0$
定义运算:
$s = a.s + b.s$
$d = \min(a.d, a.s + b.d)$
由于维护 $d$ 和 $s$ 可支持答案的快速合并以及运算满足结合律,所以可以用普通线段树来处理。
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::swap;
using std::string;
using ll = long long;
struct P {
int s, d;
P(int s=0, int d=0): s(s), d(d) {}
};
P op(P a, P b) {
return P(a.s+b.s, min(a.d, a.s+b.d));
}
P e() { return P(0, 0); }
int main() {
int n, q;
cin >> n >> q;
string s;
cin >> s;
// <数据类型,运算,单位元>
segtree<P, op, e> t(n);
auto f = [&](char c) {
return (c == '(') ? P(1, 0) : P(-1, -1);
};
rep(i, n) t.set(i, f(s[i]));
rep(qi, q) {
int type, l, r;
cin >> type >> l >> r;
--l;
if (type == 1) {
--r;
swap(s[l], s[r]);
t.set(l, f(s[l]));
t.set(r, f(s[r]));
}
else {
P p = t.prod(l, r);
if (p.s == 0 and p.d == 0) puts("Yes");
else puts("No");
}
}
return 0;
}