Parenthesis(前缀和+线段树)

Time Limit: 5 Sec Memory Limit: 128 Mb Submitted: 2291 Solved: 622

Description

Bobo has a balanced parenthesis sequence P=p1 p2…pn of length n and q questions.

The i-th question is whether P remains balanced after pai and pbi 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≤105,1≤q≤105).

The second line contains n characters p1 p2…pn.

The i-th of the last q lines contains 2 integers ai,bi (1≤ai,bi≤n,ai≠bi).

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

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

//题意: n 长字符串，m次询问，一开始括号是匹配的，问 a ，b 位置的字符调换后，是否匹配

//题解:网上很多的暴力超时代码没看懂，这题，如果，( 看成 1 ，) 看成 -1 ，其实就是求 a -- (b-1) 中前缀和最小的，在调换后是否能满足要求即可，写了个线段树求区间最小

  1 # include <cstdio>
  2 # include <cstring>
  3 # include <cstdlib>
  4 # include <iostream>
  5 # include <vector>
  6 # include <queue>
  7 # include <stack>
  8 # include <map>
  9 # include <bitset>
 10 # include <sstream>
 11 # include <set>
 12 # include <cmath>
 13 # include <algorithm>
 14 #pragma comment(linker,"/STACK:102400000,102400000")
 15 using namespace std;
 16 #define LL          long long
 17 #define lowbit(x)   ((x)&(-x))
 18 #define PI          acos(-1.0)
 19 #define INF         0x3f3f3f3f3f3f3f3f
 20 #define eps         1e-8
 21 #define MOD         1000000007
 22 
 23 inline int scan() {
 24     int x=0,f=1; char ch=getchar();
 25     while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
 26     while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
 27     return x*f;
 28 }
 29 inline void Out(int a) {
 30     if(a<0) {putchar('-'); a=-a;}
 31     if(a>=10) Out(a/10);
 32     putchar(a%10+'0');
 33 }
 34 #define MX 100005
 35 /**************************/
 36 struct Tree
 37 {
 38     int l,r;
 39     int m;
 40 }tree[MX*4];
 41 
 42 int st[MX];
 43 char str[MX];
 44 
 45 void build_tree(int l,int r,int k)
 46 {
 47     tree[k] = (Tree){l,r,0};
 48     if (l==r)
 49     {
 50         tree[k].m = st[l];
 51         return;
 52     }
 53     int mid = (l+r)/2;
 54     build_tree(l,mid,2*k);
 55     build_tree(mid+1,r,2*k+1);
 56     tree[k].m = min(tree[2*k].m,tree[2*k+1].m);
 57 }
 58 
 59 int inqy(int l,int r,int k)
 60 {
 61     if (l==tree[k].l&&r==tree[k].r)
 62         return tree[k].m;
 63 
 64     int mid = (tree[k].l+tree[k].r)/2;
 65     if (r<=mid) return inqy(l,r,2*k);
 66     else if (l>mid) return inqy(l,r,2*k+1);
 67     return min (inqy(l,mid,2*k) , inqy(mid+1,r,2*k+1));
 68 }
 69 
 70 int main()
 71 {
 72     int n,m;
 73     while (scanf("%d%d",&n,&m)!=EOF)
 74     {
 75         scanf("%s",str+1);
 76         st[0]=0;
 77         for (int i=1;i<=n;i++)
 78             st[i] = st[i-1] + (str[i]=='('?1:-1 );
 79         build_tree(1,n,1);
 80         while (m--)
 81         {
 82             int a = scan();
 83             int b = scan();
 84             if (a>b) swap(a,b);
 85 
 86             int ok=1;
 87 
 88             int sb = inqy(a,b-1,1);
 89             if (str[a]=='(') sb--;
 90             else sb++;
 91             if (str[b]==')') sb--;
 92             else sb++;
 93             if (sb<0) ok=0;
 94 
 95             if (ok)
 96                 printf("Yes
");
 97             else
 98                 printf("No
");
 99         }
100     }
101     return 0;
102 }

View Code