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

Parenthesis

 CSU - 1809 

题意：给定一个已经匹配的序列S，长为N，q次询问，每次询问交换a,b两个位置的字符，问交换后字符串是否仍然匹配

思路：定义sum[i]=到第i个位置cnt['('] -cnt[')']，显然有i∈[1,n] sum[i]>=0

假设a<b

1.若s[a]==s[b] 仍然匹配

2.若s[a]==')' && s[b]=='(' 一定匹配

3.若s[a]=='(' && s[b]==')'  

对于改变后的sum则有，sum[1~a-1]和 sum[b,n]均不变

sum[a,b-1]均 减2  。若出现i∈[a,b-1] sum[i]<0 ，就表示出现了一个无法被匹配的右括号，则对于原sum序列来说，等价于 i∈[a,b-1] min(sum[i])若<2则减2后一定为负数，代表无法完全匹配。

因此用线段树维护前缀和，对于每次交换a,b(假设a<b)的位置，只需要判断sum的区间[a,b-1]的最小值和2的关系；若小于2，则No；否则Yes。复杂度  

碰到括号匹配的题，先考虑前缀和，DP，栈

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const ll MOD=1e9+7;
const int Seed=1e7+7;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}
char s[N];
int pre[N];
struct node{
    int v;
    int mn;
}p[N<<2];
void build(int l,int r,int rt){
    p[rt].mn=1e9;
    if(l==r){
        p[rt].mn=p[rt].v=pre[l];
        return ;
    }
    int mid=l+r >> 1;
    build(l,mid,rt*2);
    build(mid+1,r,rt*2+1);
    p[rt].mn=min(p[rt*2].mn,p[rt*2+1].mn);
}

int query(int l,int r,int nl,int nr,int rt){
    if(l==nl&&r==nr){
        return p[rt].mn;
    }
    int mid=l+r >> 1;
    if(nr<=mid) return query(l,mid,nl,nr,rt*2);
    else if(nl>=mid+1)  return query(mid+1,r,nl,nr,rt*2+1);
    else    return min(query(l,mid,nl,mid,rt*2),query(mid+1,r,mid+1,nr,rt*2+1));
}

int main(){
    int n,q;
    while(scanf("%d%d",&n,&q)==2){
        scanf("%s",s+1);
        for(int i=1;i<=n;i++){
            pre[i]=pre[i-1];
            if(s[i]=='(')   ++pre[i];
            else    --pre[i];
        }
        build(1,n,1);
    ////    cout << query(1,n,2,2,1)<<endl;
        while(q--){
            int a,b;
            sf(a);sf(b);
            if(a>b) swap(a,b);
            if(s[a]==s[b]||(s[a]==')'&&s[b]=='(')){
                printf("Yes\n");
                continue;
            }
            int mn=query(1,n,a,b-1,1);
    //        cout << "mn="<<mn<<endl;
            if(mn<2)   printf("No\n");
            else    printf("Yes\n");
        }
    }
    return 0;
}