1. 写在题前
- scanf大法好，cin我真是T到不要不要的
- 本来智商就很一般
- 自己技术也是真的菜
- 菜还不努力，我太堕落了
- 好了负能量发泄完了
2. 题意
- 给你一串左右括号，然后对原来的串进行操作，操作方式是将两个位置的括号交换位置，问你这时候括号还匹配吗，注意每次操作都是对原串
3. 关于括号匹配
- 紫色数据结构那本书，在学栈的时候，有一道例题就是括号匹配，不过那道题只是让你熟悉栈的用法，真正做这种题当然不是这么搞
- 括号匹配在实际题目中大多使用前缀和来判断的，左括号是1，右括号是-1，如果最终括号匹配，那么每个位置的前缀和都是大于等于0的，且所有的总和为0
4. 关于这道题
- 这道题是交换两个位置的括号，部分前缀和在操作后会改变。对于交换(u,v)两个位置，我们先看都有哪些情况
- 如果两个都是左括号或者都是右括号，则前缀和不会发生改变，不用考虑
- 如果位置u是右括号，位置v是左括号，对于1到u-1的前缀和，不会改变，对于u到v-1，每个位置的前缀和都会+2（因为之前某个位置的数由-1变为1），对于v及v之后的前缀和，不变（因为只是交换位置，没有新增或减少任何数），所以在这种情况下，如果原来的每个位置前缀和都大于0，那么新的前缀和肯定也满足条件
- 如果位置u是左括号，位置v是右括号，那么交换位置后，u到v-1的前缀和每个都会减2（由1到-1），所以，如果这个操作后这段前缀和仍然大于0——也就是说在操作前（u,v-1）这一段的每个值都大于等于2，即最小值>=2——那么就还是满足括号匹配条件的
- 好，经过分析，如果交换前(u,v-1)这一段的前缀和的最小值>=2，则仍然满足匹配，很明显我们可以用线段树对前缀和数组维护区间最小值，那么这道题也就解了
- 另外，原始的串题目中说是满足条件的了，所以我们只需要关心操作的左右区间的最小值即可
5. 代码
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define LSon(x) ((x)<<1)
#define RSon(x) ((x)<<1|1)
const int maxn = 200020;
const int root = 1;
int n,k;
int pre[maxn];
char cc[maxn];
int node[maxn<<2];
void update(int pos)
{
node[pos] = min(node[LSon(pos)],node[RSon(pos)]);
}
void build(int l,int r,int pos)
{
node[pos]= 0;
if(l == r)
{
//cout<<l<<endl;
node[pos] = pre[l];
return;
}
int m = l+r>>1;
build(l,m,LSon(pos));
build(m+1,r,RSon(pos));
update(pos);
}
int query(int l,int r,int x,int y,int pos)
{
if(x<=l&&r<=y)
{
//cout<<"**"<<node[pos]<<"**"<<pos<<"**"<<endl;
return node[pos];
}
int res = 0x3f3f3f3f;
int m = l+r>>1;
if(x<=m)res=min(res,query(l,m,x,y,LSon(pos)));
if(y>m)res=min(res,query(m+1,r,x,y,RSon(pos)));
return res;
}
int main()
{
while(~scanf("%d%d",&n,&k))
{
memset(pre,0,sizeof(pre));
memset(node,0x3f3f3f3f,sizeof(node));
getchar();
scanf("%s",cc+1);
for(int i = 1;i<=n;i++)
{
if(cc[i] == '(')pre[i] = pre[i-1]+1;
else pre[i] = pre[i-1] - 1;
}
build(1,n,root);
//for(int i = 1;i<=2*n-1;i++)printf("%d",node[i]);
for(int i = 0;i<k;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(a>b)
{
int ccc = a;
a = b;
b = ccc;
}
if(cc[a] == '('&&cc[b] == ')')
{
int d = query(1,n,a,b-1,root);
if(d>=2)printf("Yes\n");
else printf("No\n");
}
else printf("Yes\n");
}
}
}
