括号序列
分析:
线段树维护区间(
与)
的差值:
- 首先若两个位置是相同字符,不会改变匹配形式,直接 YES;
- 若选择
)(
改变,因为原本是合法的,这样交换过后总是能再次匹配; - 若选择
()
改变,会改变原本的匹配形式,但造成影响的只有[l, r - 1]
这一段,如果(
比)
多至少 2 个,在改变过后就会使得)
仍然比(
多 ,因为原本是合法的,这样(
就会与后面的)
匹配合法;
相当于只有 query 操作
实现:
int l[N], r[N];
int a[N];
struct Node
{
int l, r;
int minv;
} tr[N << 2];
void pushup(Node &u, Node &l, Node &r)
{
u.minv = min(l.minv, r.minv);
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
if (l == r)
tr[u] = {l, l, a[l]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(Lson), build(Rson);
pushup(u);
}
}
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
return tr[u].minv;
else
{
int res = INF;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid)
res = min(res, query(u << 1, l, r));
if (r > mid)
res = min(res, query(u << 1 | 1, l, r));
return res;
}
}
void solve()
{
for (int i = 1; i <= n; i++)
l[i] = r[i] = 0;
cin >> s;
s = " " + s;
for (int i = 1; i <= n; i++)
{
if (s[i] == '(')
{
l[i] = l[i - 1] + 1;
r[i] = r[i - 1];
}
else
{
l[i] = l[i - 1];
r[i] = r[i - 1] + 1;
}
a[i] = l[i] - r[i];
}
build(1, 1, n);
while (q--)
{
int x, y;
cin >> x >> y;
if (x > y)
swap(x, y);
if (s[x] == '(' && s[y] == ')')
{
if (query(1, x, y - 1) >= 2)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
else
cout << "Yes" << endl;
}
}
标签:匹配,改变,--,tr,括号,int,query,CSG1140
From: https://www.cnblogs.com/Aidan347/p/17259635.html