V-Parenthesis 前缀+ZKW线段树或RMQ

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:

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').

题意就是给出一个正确配对的括号序列，问交换两个括号以后是否依旧正确配对，一般括号配对都可以使用遇到左括号加一，遇到右括号减一的方法，中间过程中不能出现负值，否则配对失败，这道题也可以这样做，先求出前缀和，如:

编号: 1 2 3 4 5 6 7 8

( ( ( ) ) ) ( )

前缀: 1 2 3 2 1 0 1 0

有两种仍然可以配对的交换:1.当交换的两个括号相同时,2.ai是右括号，bi是左括号时，根据示例可以看出；

唯一一种可能发生不配对的交换:ai是左括号，bi是右括号；当有右括号加入ai位置时，从ai位置到bi-1位置的前缀和全部都要减2，所以ai到bi-1区间内最小值至少为2，这样就变成了查询区间最小值问题了，可以用线段树，也可以RMQ（代码待补）；因为刚刚学习线段树，又刚好听说ZKW线段树代码比较精简，所以临时现去学习了一下，结果发现好多给的示例代码都是错的。。。这个版本可能也有错，但是AC了就好。。。哈哈哈哈哈哈哈哈哈嗝。。。。

zkw线段树:

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

const int N =  + ;

const int INF = (<<);

int sum[N],T[N<<],cnt,M;

char ch[N];

void Build(int n){

    int i;

    for(M=;M<=n+;M*=);

    for(i=+M;i<=n+M;i++) T[i] = sum[cnt++];

    for(i=M-;i;i--) T[i]=min(T[i<<],T[i<<|]);

}

void Update(int n,int V){

    for(T[n+=M]=V,n/=;n;n/=)

        T[n]=min(T[n<<],T[n<<|]);

}

int Query(int s,int t){

    int minc=INF;

    for(s=s+M-,t=t+M+;s^t^;s/=,t/=){

        if(~s&) minc=min(minc,T[s^]);

        if(t&) minc=min(minc,T[t^]);

    }

    return minc;

}

int main(){

    int n,q,a,b;

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

        scanf("%s",ch+);

        sum[] = ;

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

            if(ch[i]=='(') sum[i]=sum[i-]+;

            else sum[i]=sum[i-]-;

        }

        cnt = ;

        Build(n);

        for(int i=;i<q;i++){

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

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

            if(ch[a]==ch[b] || (ch[a]==')'&&ch[b]=='(')){ printf("Yes\n"); continue; }

            int ret = Query(a,b-);

            printf("%s\n",ret>=?"Yes":"No");

        }

    }

    return ;

}

RMQ:

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

const int N =  + ;

const int INF = (<<);

int sum[N],dp[N][],cnt,n;

char ch[N];

void RMQ_Init(){

    memset(dp,,sizeof(dp));

    for(int i=;i<n+;i++) dp[i][] = sum[i];

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

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

        dp[i][j] = min(dp[i][j-],dp[i+(<<(j-))][j-]);

}

int RMQ(int L,int R){

    int k = ;

    while((<<(k+))<=R-L+) k++;

    return min(dp[L][k],dp[R-(<<k)+][k]);

}

int main(){

    int q,a,b;

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

        scanf("%s",ch+);

        sum[] = ;

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

            if(ch[i]=='(') sum[i]=sum[i-]+;

            else sum[i]=sum[i-]-;

        }

        cnt = ;

        RMQ_Init();

        for(int i=;i<q;i++){

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

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

            if(ch[a]==ch[b] || (ch[a]==')'&&ch[b]=='(')){ printf("Yes\n"); continue; }

            int ret = RMQ(a,b-);

            printf("%s\n",ret>=?"Yes":"No");

        }

    }

    return ;

}

巴特西

V-Parenthesis 前缀+ZKW线段树或RMQ

最新文章

热门文章