2016年省赛G题， Parenthesis

Problem G: Parenthesis

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 398 Solved: 75
[Submit][Status][Web Board]

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

比赛的时候，老O查个单词，我后来又查了一下，单词没看完意思，说是"不规则的"，发现里面还有一个括号的意思，也就是说只有括号，当时还以为有其他字符，想了好久，好像其他字符在这里没有起到作用
然后是第二个条件，可不可以反推，纠结了好久，最后还是直接模拟了一遍，虽然已经知道会tle，还是写了一下，当时只有这个题目A得人比较多一点。

解题报告：
1、只有括号
2、3个条件就是括号匹配的实质。

思路：
　　直接栈模拟是肯定不行的，就算要用栈模拟也不是普通的栈模拟，直接记录左括号的个数，这样模拟。然后这里询问次数10^5，n = 10^5，就是10^10了，这里用线段树优化，每次)(区间都是+2,
　　直接yes,要是()，就看-2是否是小于0.

#include <stdio.h>

#include <algorithm>

using namespace std;

int temp[];

char str[];

#define INF 0x3f3f3f3f

struct node

{

    int left,right,val;

} c[*];

void build_tree(int l,int r,int root)

{

    c[root].left=l;

    c[root].right=r;

    if(l==r)

    {

        c[root].val=temp[l];

        return ;

    }

    int mid=(l+r)/;

    build_tree(l,mid,root*);

    build_tree(mid+,r,root*+);

    c[root].val=min(c[root*].val,c[root*+].val);

}

void query(int l,int r,int &min1,int root)

{

    if(c[root].left==l&&c[root].right==r)

    {

        min1=c[root].val;

        return ;

    }

    int mid=(c[root].left+c[root].right)/;

    if(mid<l)

        query(l,r,min1,root*+);

    else if(mid>=r)

        query(l,r,min1,root*);

    else

    {

        int min2;

        query(l,mid,min1,root*);

        query(mid+,r,min2,root*+);

        min1=min(min1,min2);

    }

}

int main()

{

    int n,m;

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

    {

        scanf("%s",str+);

        int counts = ;

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

        {

            if(str[i]=='(')

                temp[i] = ++counts;

            else temp[i] = --counts;

        }

        build_tree(,n,);

        int ls,rs;

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

        {

            scanf("%d%d",&ls,&rs);

            if(ls > rs)

                swap(ls,rs);

            if(str[ls]==')'&&str[rs]=='(')

            {

                puts("Yes");

                continue;

            }

            if(str[ls]==str[rs])

            {

                puts("Yes");

                continue;

            }

            if(str[ls]=='('&&str[rs]==')')

            {

                int mins = INF;

                query(ls,rs-,mins,);

                if(mins<)

                    puts("No");

                else puts("Yes");

                continue;

            }

        }

    }

    return ;

}

巴特西