Gym 100803G Flipping Parentheses

题目链接：http://codeforces.com/gym/100803/attachments/download/3816/20142015-acmicpc-asia-tokyo-regional-contest-en.pdf

题意：给你一些匹配好的括号，长为n，有m个操作，每次操作把其中一个"("改为")"，或者把其中一个")"改为"(",问你改动一个单括号，使得改后的括号序列任然完美匹配，如果有多种该法，求出最前面的。

思路：可以分两种情况分类讨论，先求出所有下标的前缀和，如果是第一种情况，那么只要从左到右找到第一个")"就行了，可以用set维护，如果是第二种情况，那么可以用线段树维护区间的最小值，然后用二分查找出最前面的一个大于等于2，且后面的前缀和的值都大于等于2的下标。

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<string>

#include<algorithm>

using namespace std;

typedef long long ll;

#define maxn 300030

char s[maxn];

int sum[maxn];

#define inf 888888888

struct node{

    int l,r,minx,add;

}b[4*maxn];

set<int>myset;

set<int>::iterator it;

void build(int l,int r,int i)

{

    int mid;

    b[i].l=l;b[i].r=r;b[i].add=0;

    if(l==r){

        b[i].minx=sum[l];

        return;

    }

    mid=(l+r)/2;

    build(l,mid,i*2);

    build(mid+1,r,i*2+1);

    b[i].minx=min(b[i*2].minx,b[i*2+1].minx);

}

void update(int l,int r,int add,int i)

{

    int mid;

    if(b[i].l==l && b[i].r==r){

        b[i].add+=add;

        b[i].minx+=add;

        return;

    }

    if(b[i].add){

        b[i*2].add+=b[i].add;

        b[i*2].minx+=b[i].add;

        b[i*2+1].add+=b[i].add;

        b[i*2+1].minx+=b[i].add;

        b[i].add=0;

    }

    mid=(b[i].l+b[i].r)/2;

    if(r<=mid)update(l,r,add,i*2);

    else if(l>mid)update(l,r,add,i*2+1);

    else {

        update(l,mid,add,i*2);

        update(mid+1,r,add,i*2+1);

    }

    b[i].minx=min(b[i*2].minx,b[i*2+1].minx);

}

int question(int l,int r,int i)

{

    int mid;

    if(b[i].l==l && b[i].r==r){

        return b[i].minx;

    }

    if(b[i].add){

        b[i*2].add+=b[i].add;

        b[i*2].minx+=b[i].add;

        b[i*2+1].add+=b[i].add;

        b[i*2+1].minx+=b[i].add;

        b[i].add=0;

    }

    mid=(b[i].l+b[i].r)/2;

    if(r<=mid)return question(l,r,i*2);

    else if(l>mid)return question(l,r,i*2+1);

    else {

        return min(question(l,mid,i*2),question(mid+1,r,i*2+1)   );

    }

    b[i].minx=min(b[i*2].minx,b[i*2+1].minx);

}

int main()

{

    int n,m,i,j,c,l,r,mid;

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

    {

        scanf("%s",s+1);

        sum[0]=0;

        myset.clear();

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

            if(s[i]=='('){

                sum[i]=sum[i-1]+1;

            }

            else{

                sum[i]=sum[i-1]-1;

                myset.insert(i);

            }

        }

        build(1,n,1);

        for(i=1;i<=m;i++){

            scanf("%d",&c);

            if(s[c]=='('){

                s[c]=')';

                myset.insert(c);

                update(c,n,-2,1);

                it=myset.begin();

                cout<<*it<<endl;

                myset.erase(it);

                update(*it,n,2,1);

                s[*it]='(';

            }

            else if(s[c]==')'){

                s[c]='(';

                myset.erase(c);

                update(c,n,2,1);

                l=1;r=n;

                while(l<=r){

                    mid=(l+r)/2;

                    if(question(mid,n,1)>=2)r=mid-1;

                    else l=mid+1;

                }

                printf("%d\n",l);

                s[l]=')';

                update(l,n,-2,1);

                myset.insert(l);

            }

        }

    }

    return 0;

}

巴特西

Gym 100803G Flipping Parentheses

最新文章

热门文章