Problem
acm.csu.edu.cn/csuoj/problemset/problem?pid=1809
vjudge.net/contest/161962#problem/G
Reference
blog.csdn.net/l954688947/article/details/52431152
blog.csdn.net/ACMore_Xiong/article/details/52426946
Meaning
给出一个平衡的括号序列,q 个询问,每次问交换 a 和 b 位置的括号后得到的序列是否仍是平衡括号序列。
Analysis
如果要交换的两个括号是相同的,那肯定没问题。
如果是将“…)…(…”换成“…(…)…”,题解说没问题,也找不出反例,但总觉得…有点玄学。
如果是将“…(…)…”换成“…)…(…”,就有可能导致不匹配。
处理一个前缀和:'(' 权值是 1,')' 权值是 -1。这样平衡的序列在任意位置的前缀和都是非负的。
易知,前两种交换法都不会使得任何位置的前缀和减小,而第三种会使得 [ a , b ) 各位置上的前缀和 -2,如果减出了负数,就说明出现了不平衡的情况。
所以只在进行第三种交换时,查询 [ a , b ) 上的最小值是否小于 2 即可。
Code
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100000;
char s[N+3];
int pre[N+1], tree[N+1<<1];
inline void pushup(int x)
{
tree[x] = min(tree[x<<1], tree[x<<1|1]);
}
void build(int l, int r, int id)
{
if(l == r)
{
tree[id] = pre[l];
return;
}
int m = l + r >> 1;
build(l, m, id<<1);
build(m+1, r, id<<1|1);
pushup(id);
}
int query(int ql, int qr, int l, int r, int id)
{
if(ql <= l && r <= qr)
return tree[id];
if(r < ql || qr < l)
return N;
int m = l + r >> 1;
return min(query(ql, qr, l, m, id<<1),
query(ql, qr, m+1, r, id<<1|1));
}
int main()
{
int n, q;
while(~scanf("%d%d", &n, &q))
{
scanf(" %s", s+1);
pre[0] = 0;
for(int i=1; i<=n; ++i)
if(s[i] == '(')
pre[i] = pre[i-1] + 1;
else
pre[i] = pre[i-1] - 1;
build(1, n, 1);
for(int a, b; q--; )
{
scanf("%d%d", &a, &b);
if(a > b)
swap(a, b);
if(s[a] == '(' && s[b] == ')')
if(query(a, b-1, 1, n, 1) < 2)
puts("No");
else
puts("Yes");
else
puts("Yes");
}
}
return 0;
}