【数字_ID】CSU-1809-Parenthesis(线段树+

• 编辑：邓楚盟
• 时间：2018年5月22日

1. 写在题前

• scanf大法好，cin我真是T到不要不要的
• 本来智商就很一般
• 自己技术也是真的菜
• 菜还不努力，我太堕落了
• 好了负能量发泄完了

2. 题意

• 给你一串左右括号，然后对原来的串进行操作，操作方式是将两个位置的括号交换位置，问你这时候括号还匹配吗，注意每次操作都是对原串

3. 关于括号匹配

• 紫色数据结构那本书，在学栈的时候，有一道例题就是括号匹配，不过那道题只是让你熟悉栈的用法，真正做这种题当然不是这么搞
• 括号匹配在实际题目中大多使用前缀和来判断的，左括号是1，右括号是-1，如果最终括号匹配，那么每个位置的前缀和都是大于等于0的，且所有的总和为0

4. 关于这道题

• 这道题是交换两个位置的括号，部分前缀和在操作后会改变。对于交换(u,v)两个位置，我们先看都有哪些情况
  1. 如果两个都是左括号或者都是右括号，则前缀和不会发生改变，不用考虑
  2. 如果位置u是右括号，位置v是左括号，对于1到u-1的前缀和，不会改变，对于u到v-1，每个位置的前缀和都会+2（因为之前某个位置的数由-1变为1），对于v及v之后的前缀和，不变（因为只是交换位置，没有新增或减少任何数），所以在这种情况下，如果原来的每个位置前缀和都大于0，那么新的前缀和肯定也满足条件
  3. 如果位置u是左括号，位置v是右括号，那么交换位置后，u到v-1的前缀和每个都会减2（由1到-1），所以，如果这个操作后这段前缀和仍然大于0——也就是说在操作前（u,v-1）这一段的每个值都大于等于2，即最小值>=2——那么就还是满足括号匹配条件的
• 好，经过分析，如果交换前(u,v-1)这一段的前缀和的最小值>=2，则仍然满足匹配，很明显我们可以用线段树对前缀和数组维护区间最小值，那么这道题也就解了
• 另外，原始的串题目中说是满足条件的了，所以我们只需要关心操作的左右区间的最小值即可

5. 代码

#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<iostream>

using namespace std;


#define LSon(x) ((x)<<1)
#define RSon(x) ((x)<<1|1)


const int maxn = 200020;
const int root = 1;
int n,k;


int pre[maxn];
char cc[maxn];
int node[maxn<<2];

void update(int pos)
{
    node[pos] = min(node[LSon(pos)],node[RSon(pos)]);
}

void build(int l,int r,int pos)
{
    node[pos]= 0;
    if(l == r)
    {
        //cout<<l<<endl;
        node[pos] = pre[l];
        return;
    }
    int m = l+r>>1;
    build(l,m,LSon(pos));
    build(m+1,r,RSon(pos));
    update(pos);
}


int query(int l,int r,int x,int y,int pos)
{
    if(x<=l&&r<=y)
    {
    //cout<<"**"<<node[pos]<<"**"<<pos<<"**"<<endl;
        return node[pos];
    }
    int res = 0x3f3f3f3f;
    
    int m = l+r>>1;
    if(x<=m)res=min(res,query(l,m,x,y,LSon(pos)));
    if(y>m)res=min(res,query(m+1,r,x,y,RSon(pos)));
    return res;
}

int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        memset(pre,0,sizeof(pre));
        memset(node,0x3f3f3f3f,sizeof(node));
        getchar();
        scanf("%s",cc+1);
        for(int i = 1;i<=n;i++)
        {

            if(cc[i] == '(')pre[i] = pre[i-1]+1;
            else pre[i] = pre[i-1] - 1;
        }

        build(1,n,root);
        //for(int i = 1;i<=2*n-1;i++)printf("%d",node[i]);
        for(int i = 0;i<k;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(a>b)
            {
                int ccc = a;
                a = b;
                b = ccc;
            }
            
            if(cc[a] == '('&&cc[b] == ')')
            {

                int d = query(1,n,a,b-1,root);
                if(d>=2)printf("Yes\n");
                else printf("No\n");
            }
            else printf("Yes\n");
        }
    }
}