第十二届湖南省赛G - Parenthesis （树状数组维护）-白红宇

第十二届湖南省赛G - Parenthesis （树状数组维护）

阅读量：5302 次

发布时间：2019-06-14

本文共 3030 字，大约阅读时间需要 10 分钟。

Bobo has a balanced parenthesis sequence P=p

₁ p

₂…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:

S is empty;

or there exists balanced parenthesis sequence A,B such that S=AB;

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

⁵,1≤q≤10

⁵).

The second line contains n characters p

₁ p

₂…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).

OutputFor 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

题意：

给你一个长度为N个合法的括号字符串，然后有 Q 个询问，每一个询问Q，有一个L和R，如果字符串中的L和R位置的两个字符交换后，括号字符串仍然合法的话，那么输出Yes，否则输出No。

思路：

可以用树状数组维护一下，

我们定义如下，如果字符是'(' 我们定他的权值为-1，')' 定义权值为 +1，

我们容易知道，一个合法的字符串的总权值和是0.，并且一个合法的括号串，不存在任意一个位置i，1~i到sum和不大于0。

因为题目给的是一个合法的字符串，那么每一次询问的时候，我们把对应的位置的数值给改变一下，

然后检测如下条件是否成立。

sum（1~l），sum（ 1~l+1 ），sum（1~r），sum（ 1~ r+1 ）

需要以上的值均小于等于0，那么这个字符串一定是合法的。

我们可以通过树状数组来做，因为基础的树状数组模板就有单点修改，区间查询的功能。

细节见代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #define ALL(x) (x).begin(), (x).end()#define rt return#define dll(x) scanf("%I64d",&x)#define xll(x) printf("%I64d\n",x)#define sz(a) int(a.size())#define all(a) a.begin(), a.end()#define rep(i,x,n) for(int i=x;i
                
                 #define pll pair
                 
                  #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define MS0(X) memset((X), 0, sizeof((X)))#define MSC0(X) memset((X), '\0', sizeof((X)))#define pb push_back#define mp make_pair#define fi first#define se second#define eps 1e-6#define gg(x) getInt(&x)#define db(x) cout<<"== [ "<
                  
                   <<" ] =="<
                   
                    0) { res+=tree[x]; x-=lowbit(x); } return res;}int main(){// freopen("D:\\common_text\\code_stream\\in.txt","r",stdin); //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout); while(~scanf("%d %d",&n,&q)) { MS0(tree); scanf("%s",s+1); repd(i,1,n) { if(s[i]=='(') { add(i,-1); }else { add(i,1); } } int l,r; while(q--) { scanf("%d %d",&l,&r); if(s[l]==s[r]) { printf("Yes\n"); }else { if(s[l]=='(') { // 改 为 ) -1 -> 1 add(l,2); // 1 -> -1 add(r,-2); }else { add(l,-2); add(r,2); } if(query(l)<=0&&query(l+1)<=0&&query(r)<=0&&query(r+1)<=0&&query(n)==0) { printf("Yes\n"); }else { printf("No\n"); } if(s[l]=='(') { add(l,-2); add(r,2); }else { add(l,2); add(r,-2); } } } } return 0;}inline void getInt(int* p) { char ch; do { ch = getchar(); } while (ch == ' ' || ch == '\n'); if (ch == '-') { *p = -(getchar() - '0'); while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 - ch + '0'; } } else { *p = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 + ch - '0'; } }}

转载于:https://www.cnblogs.com/qieqiemin/p/10686320.html

你可能感兴趣的文章