2016年湖南省第十二届大学生计算机程序设计竞赛---Parenthesis（线段树求区间最值）

原题链接

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1809

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

Sample Output

No

Yes

No

Source

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

题意：给了一个平衡的括号序列s（平衡是指括号匹配正常）现在q次询问，每次输入两个数a、b 问将s[a] s[b]交换后是否任然平衡，平衡则输出“Yes” 否则输出“No”；

思路：定义数组num[] ，num[i]表示s[1]到s[i]中左括号数减去右括号数的差值，分析可知因为s是平衡括号序列，那么num[i]>=0 令a<b ,那么交换s[a] s[b]后，只对num[a]~num[b-1]产生影响，并且交换后当num[k]<0（a<=k<b）时表示不平衡,而只有s[a]='(' s[b]=')' 交换后才可能使num[k]<0 。所以特判当s[a]='(' s[b]=')'时，用线段树求区间a~b-1的最小值，当最小值小于2时，即交换后不平衡，为什么呢？ s[a]='(' s[b]=')'交换后num[a]~num[b-1]都减2；

代码如下：

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <cmath>

#define eps 1e-8

#define maxn 105

#define inf 0x3f3f3f3f3f3f3f3f

#define IN freopen("in.txt","r",stdin);

using namespace std;

char s[];

int num[];

int a,b;

struct Node

{

    //int l,r;

    int v;

}node[*];

void build(int l,int r,int i)

{

    if(l==r) {

       node[i].v=num[l];

       return;

    }

    int mid=(l+r)>>;

    build(l,mid,i<<);

    build(mid+,r,i<<|);

    node[i].v=min(node[i<<].v,node[i<<|].v);

}

void query(int l,int r,int &tmp,int i)

{

    if(l>=a&&r<=b) { tmp=node[i].v; return; }

    int mid=(l+r)>>;

    if(mid>=b) query(l,mid,tmp,i<<);

    else  if(mid<a) query(mid+,r,tmp,i<<|);

    else {

          int tmp2;

          query(l,mid,tmp,i<<);

          query(mid+,r,tmp2,i<<|);

          tmp=min(tmp,tmp2);

    }

}

int main()

{

    int n,q;

    while(scanf("%d%d",&n,&q)!=EOF)

    {

        scanf("%s",s+);

        num[]=;

        for(int i=;i<=n;i++)

        {

            num[i]=num[i-];

            if(s[i]=='(') num[i]++;

            else  num[i]--;

        }

        build(,n,);

        while(q--)

        {

            scanf("%d%d",&a,&b);

            if(a>b) swap(a,b);

            if(s[a]==s[b]||s[a]==')'&&s[b]=='(')  puts("Yes");

            else

            {

                b--;

                int tmp=;

                query(,n,tmp,);

                if(tmp<) puts("No");

                else      puts("Yes");

            }

        }

    }

    return ;

}

/**

8 8

(())(())

2 7

*/

秒客网