题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1809
Bobo has a balanced parenthesis sequence P=p 1 p 2…p n of length n and q questions.
The i-th question is whether P remains balanced after p ai and p bi swapped. Note that questions are individual so that they have no affect on others.
Parenthesis sequence S is balanced if and only if:
1. S is empty;
2. or there exists balanced parenthesis sequence A,B such that S=AB;
3. or there exists balanced parenthesis sequence S' such that S=(S').
Input
The input contains at most 30 sets. For each set:
The first line contains two integers n,q (2≤n≤10 5,1≤q≤10 5).
The second line contains n characters p 1 p 2…p n.
The i-th of the last q lines contains 2 integers a i,b i (1≤a i,b i≤n,a i≠b i).
Output
For each question, output " Yes" if P remains balanced, or " No" otherwise.
Sample Input
4 2
(())
1 3
2 3
2 1
()
1 2
Sample Output
No
Yes
No
题意：
现在给出长度为n的一串圆括号串，保证是平衡的括号串；
再给出q个查询，每个查询有两个值a,b，代表询问交换P[a]和P[b]，会不会使得括号串变得不平衡。
题解：
首先，我们定义一个preSum数组，代表了这括号序列的前缀和，遇到一个'('就加上1，遇到一个')'就减去1；
这样一来，该括号序列为平衡序列 $\Leftrightarrow$ preSum[n]==0，且对于$\forall$i=1~n都有preSum[i]≥0；
那么我们有以下三种情况：
- P[a]==P[b]，这样情况显然交换一下和原来没有区别，显然是保持平衡的；
- P[a]=')'且P[b]='('，这种情况下，preSum[1]~preSum[a-1]不会有任何变动，preSum[a]~preSum[b-1]都会$+=2$，preSum[b]~preSum[n]也不会有任何变动，这样一来，交换后产生的新的括号序列，依然满足preSum[n]==0，且对于$\forall$i=1~n都有preSum[i]≥0，那么显然该括号序列还是平衡序列；
- P[a]='('且P[b]=')'，这种情况下，preSum[1]~preSum[a-1]不会有任何变动，preSum[a]~preSum[b-1]都会$-=2$，preSum[b]~preSum[n]不会有任何变动，那么显然关键就在preSum[a]~preSum[b-1]上了，我们知道一旦有一个preSum[i]<0，这个括号序列就不平衡了，所以我们必须保证preSum[a]~preSum[b-1]都大于等于2才行。
所以，我们可以使用线段树或者RMQ维护preSum[]数组的区间最小值，对每次查询只要查询出[a,b]区间内preSum[i]的最小值有没有比2大就可以了。
AC代码：
①线段树：
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL; const int maxn=1e5+;
const int INF=0x3f3f3f3f; int n,q;
char str[maxn];
int preSum[maxn]; struct Node{
int l,r;
int val;
}node[*maxn];
void pushup(int root)
{
node[root].val=min(node[root*].val,node[root*+].val);
}
void build(int root,int l,int r)
{
node[root].l=l; node[root].r=r;
if(l==r) node[root].val=preSum[l];
else
{
int mid=l+(r-l)/;
build(root*,l,mid);
build(root*+,mid+,r);
pushup(root);
}
}
int query(int root,int st,int ed)
{
if(ed<node[root].l || node[root].r<st) return INF;
if(st<=node[root].l && node[root].r<=ed) return node[root].val;
else return min(query(root*,st,ed),query(root*+,st,ed));
} int main()
{
while(scanf("%d%d",&n,&q)!=EOF)
{
scanf("%s",str+); preSum[]=;
for(int i=;i<=n;i++) preSum[i]=preSum[i-]+(str[i]=='('?:-); build(,,n);
for(int i=,a,b;i<=q;i++)
{
scanf("%d%d",&a,&b);
if(a>b) swap(a,b); if( str[a]==str[b] || (str[a]==')' && str[b]=='(') ) printf("Yes\n");
else if(query(,a,b-)>=) printf("Yes\n");
else printf("No\n");
}
}
}
②RMQ：
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL; const int maxn=1e5+;
const int INF=0x3f3f3f3f; int n,q;
char str[maxn];
int preSum[maxn]; struct _RMQ{
int Mnum[maxn][]; //int(log(maxn)/log(2.0))
void init(int num[])
{
for(int i=;i<=n;i++) Mnum[i][]=num[i];
int j_max=(log(n)/log());
for(int j=;j<=j_max;j++)
{
for(int i=;i<=n;i++)
{
if(i+(<<j)- <= n)
Mnum[i][j]=min(Mnum[i][j-],Mnum[i+(<<(j-))][j-]);
}
}
}
int query(int l,int r)
{
int k=log(r-l+)/log();
return min(Mnum[l][k],Mnum[r-(<<k)+][k]);
}
}RMQ; int main()
{
while(scanf("%d%d",&n,&q)!=EOF)
{
scanf("%s",str+); preSum[]=;
for(int i=;i<=n;i++) preSum[i]=preSum[i-]+(str[i]=='('?:-); RMQ.init(preSum);
for(int i=,a,b;i<=q;i++)
{
scanf("%d%d",&a,&b);
if(a>b) swap(a,b); if( str[a]==str[b] || (str[a]==')' && str[b]=='(') ) printf("Yes\n");
else if(RMQ.query(a,b-)>=) printf("Yes\n");
else printf("No\n");
}
}
}