括号匹配（线段树）

个人心得：近期状态不佳，不光题目看错而且思维也是很凌乱，赶紧把杂事解决好认真锻炼思维吧。

这一题我真的是想不到用线段树的，贼水，看题解也看了半天，因为若不满足的话必须在改变的俩个数之间

存在着i使前面的多一个“）“，所以只需要用线段树进行最小值维护就好了

首先预处理出一个前缀和sum【i】，设定(表示1，)表示-1.那么我们开始分类讨论：

①a【x】==a【y】，那么结果一定是Yes.

②a【x】==‘)’&&a【y】==‘(’，那么结果也一定是Yes.因为如果左边的右括号放置在了右边，可以和放置在左边的这个左括号进行匹配，原串保证是匹配的，所以这样交换的结果也一定是Yes.

③a【x】==‘(’&&a【y】==‘)’，那么考虑对前缀和的影响：

撤销x位子上的左括号：从x-------------->n 前缀和全部减去1

撤销y位子上的右括号：从y-------------->n 前缀和全部加上1

放置x位子上那个右括号：从x----------->n 前缀和全部减去1

放置y位子上那个左括号：从y----------->n 前缀和全部加上1

显然，如果有某个前缀和的位子上出现了负数，那么此时这个字符串一定是构不成括号匹配的，所以我们只要判定影响到的部分是否会出现负数即可。

显然，从y---------->n的部分都加上了2，从x---------->y-1的部分都减去了1.

那么我们只要查询之前前缀和中区间【x，y-1】中的最小值是否大于等于2即可，如果是，结果就是Yes.否则就是No.

题目：

Description

Bobo has a balanced parenthesis sequence P=p₁ p₂…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⁵,1≤q≤10⁵).

The second line contains n characters p₁ p₂…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

Hint

Source

湖南省第十二届大学生计算机程序设计竞赛

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=100005;
 6 char s[maxn];
 7 int sum[maxn];
 8 int n,q,l,r,i,j;
 9 struct node
10 {
11     int l,r,minn;
12 }tr[maxn*4];//一定要*4
13 void build(int id,int l,int r)
14 {
15     tr[id].l=l;
16     tr[id].r=r;
17     if(l==r)
18     {
19         tr[id].minn=sum[l];
20     }
21     else
22     {
23         int mid=(l+r)/2;
24         build(id*2,l,mid);
25         build(id*2+1,mid+1,r);
26         tr[id].minn=min(tr[id*2].minn,tr[id*2+1].minn);
27     }
28 }
29 int quary(int id,int l,int r)
30 {
31     if(l<=tr[id].l&&tr[id].r<=r)
32         return tr[id].minn;
33     else
34     {
35         int mid=(tr[id].l+tr[id].r)/2;
36         if(r<=mid)
37             return quary(id*2,l,r);
38         else if(l>mid)
39             return quary(id*2+1,l,r);
40         else
41         {
42             int x=quary(id*2,l,r);
43             int y=quary(id*2+1,l,r);
44             return min(x,y);
45         }
46     }
47 }
48 int main()
49 {
50     while(~scanf("%d%d",&n,&q))
51     {
52         int ans=0;
53         scanf("%s",s+1);
54         if(s[1]='(') sum[1]=1;
55         else sum[1]=-1;
56         for(i=2;i<=n;i++)
57         {
58             if(s[i]=='(')
59                sum[i]=sum[i-1]+1;
60             else
61                sum[i]=sum[i-1]-1;
62         }
63         build(1,1,n);
64         for(i=0;i<q;i++)
65         {
66             scanf("%d%d",&l,&r);
67             if(l>r) swap(l,r);
68             if(s[l]=='('&&s[r]==')')
69             {
70                 if(quary(1,l,r-1)-2>=0)
71                     printf("Yes
");
72                 else
73                     printf("No
");
74             }
75             else printf("Yes
");
76         }
77     }
78     return 0;
79 }