首页 > 代码库 > Parenthesis

Parenthesis

2024-08-13 06:54:15   220人阅读

 
G - Parenthesis
Time Limit:5000MS     Memory Limit:131072KB     64bit IO Format:%lld & %llu

Description

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 32 32 1()1 2

Sample Output

NoYesNo

Hint

 思路:线段树；
 当括号匹配时我们有所有的前缀和sum〉=0;那么当我们交换两个括号时仅会改变sum[a]----sum[b]的值 ，并且只有当a为（  b为 ）才可能不匹配，那么当这两交换，这个区间段所有的值会减去2，那么我们用线段树维护sum的最小值即可，然后与2比较。复杂n*log(n)
 1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<queue> 5 #include<stdlib.h> 6 #include<string.h> 7 using namespace std; 8 char str[100005]; 9 int tree[100005*4];10 int ans[100005];11 void build(int l,int r,int k);12 int ask(int l,int r,int k,int nn,int mm);13 int main(void)14 {15     int n,m;16     while(scanf("%d %d",&n,&m)!=EOF)17     {18         scanf("%s",str);19         int l = strlen(str);20         ans[0] = 0;21         for(int i = 0; i < l; i++)22         {23             if(str[i] == ‘(‘)24             {25                 ans[i+1] = 1;26             }27             else ans[i+1] = -1;28         }29         for(int i = 1; i <= l; i++)30         {31             ans[i] = ans[i] + ans[i-1];32         }33         build(1,l,0);34         while(m--)35         {36             int x,y;37             scanf("%d %d",&x,&y);38             if(x > y)swap(x,y);39             if(str[x-1]==str[y-1]||str[x-1]==‘)‘)40             {41                 printf("Yes\n");42             }43             else44             {45                 int ak = ask(x,y-1,0,1,l);46                 if(ak<2)47                     printf("No\n");48                 else printf("Yes\n");49             }50         }51     }return 0;52 }53 void build(int l,int r,int k)54 {55     if(l == r)56     {57         tree[k] = ans[l];58     }59     else60     {61         build(l,(l+r)/2,2*k+1);62         build((l+r)/2+1,r,2*k+2);63         tree[k] = min(tree[2*k+1],tree[2*k+2]);64     }65 }66 int ask(int l,int r,int k,int nn,int mm)67 {68     if(nn>r||mm<l)69     {70       return 1e9;71     }72     else if(l<=nn&&r>=mm)73     {74         return tree[k];75     }76     else77     {78         int x = ask(l,r,2*k+1,nn,(nn+mm)/2);79         int y = ask(l,r,2*k+2,(nn+mm)/2+1,mm);80         return min(x,y);81     }82 }

 

 

Parenthesis


联系
我们