CodeForces Gym - 100803G Flipping Parentheses(线段树)

Posted on | In ,

思路

题意是给定一个匹配好的括号序列，后面有Q次操作，每次操作将第q位的括号反转，你需要找到一个位置反转该位置上的括号让它重新匹配。位置要求是所有可行位置中最左边的。
我们令左括号为1，右括号为-1，并求出前缀和。考虑将右括号变为左括号的过程，我们能发现该操作的影响是从该位置到序列尾部的前缀和加2。将左括号变为右括号则是区间-2。为了反转后的括号序列是合法的，我们的前缀和中不能出现小于0的数。因而对操作是右括号变为左括号的情况我们可以将问题转化为哪个位置到末尾的最小值是2，以上所有操作可以使用二分+区间更新线段树实现。而对于左括号变为右括号的操作，我们只要维护一个set保存右括号的下标，然后取出最小的下标即可（很简单的思路，简单画一画就能发现）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
#define ll long long
#define INF 0x7fffffff
#define inf 0x7fffffffffffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))
#define sqr(x) ((x)*(x))

using namespace std;

const int MAXN=300005;
int a[MAXN];
char str[MAXN];
set<int> dict;
struct node{
    int l,r,mins,lazy;
}tree[MAXN*4];
void push_up(int root){
    tree[root].mins=min(tree[root*2].mins+tree[root*2].lazy,tree[root*2+1].mins+tree[root*2+1].lazy);
}
void build(int l,int r,int root){\
    tree[root].l=l,tree[root].r=r,tree[root].lazy=0;
    if(l==r)tree[root].mins=a[l];
    else{
        int mid=(l+r)>>1;
        build(l,mid,root*2);
        build(mid+1,r,root*2+1);
        push_up(root);
    }
}
void push_down(int root){
    tree[root*2].lazy+=tree[root].lazy,tree[root*2+1].lazy+=tree[root].lazy;
    tree[root].mins+=tree[root].lazy;
    tree[root].lazy=0;
}
void update(int l,int r,int val,int root){
    if(l<=tree[root].l&&tree[root].r<=r)tree[root].lazy+=val;
    else{
        push_down(root);
        int mid=(tree[root].l+tree[root].r)>>1;
        if(l<=mid)update(l,r,val,root*2);
        if(r>mid)update(l,r,val,root*2+1);
        push_up(root);
    }
}
int query(int l,int r,int root){
    if(l<=tree[root].l&&tree[root].r<=r)return tree[root].mins+tree[root].lazy;
    else{
        push_down(root);
        int mid=(tree[root].l+tree[root].r)>>1;
        if(r<=mid)return query(l,r,root*2);
        else if(l>mid)return query(l,r,root*2+1);
        else{
            return min(query(l,r,root*2),query(l,r,root*2+1));
        }
    }
}

int main(){
    int N,Q,q;
    while(~scanf("%d%d",&N,&Q)){
        ms(a,0);
        scanf("%s",str);
        for(int i=0;i<N;i++){
            if(str[i]==')'){
                a[i+1]=-1;
                dict.insert(i+1);
            }
            else a[i+1]=1;
        }
        for(int i=1;i<=N;i++)a[i]+=a[i-1];
        //for(int i=1;i<=N;i++)cout<<a[i]<<endl;
        build(1,N,1);
        for(int i=0;i<Q;i++){
            scanf("%d",&q);
            if(str[q-1]=='('){
                str[q-1]=')';
                dict.insert(q);
                update(q,N,-2,1);
                printf("%d\n",*dict.begin());
                update(*dict.begin(),N,2,1);
                str[*dict.begin()-1]='(';
                dict.erase(dict.begin());
            }
            else{
                str[q-1]='(';
                dict.erase(q);
                update(q,N,2,1);
                int L=1,R=N;
                while(L<R){
                    int mid=(L+R)>>1;
                    if(query(mid,R,1)>=2)R=mid;
                    else L=mid+1;
                }
                str[L-1]=')';
                update(L,N,-2,1);
                printf("%d\n",L);
                dict.insert(L);
                /*for(int j=1;j<=N;j++){
                    //cout<<query(i,N,1)<<endl;
                    if(query(j,N,1)==2){
                        str[j-1]=')';
                        update(j,N,-2,1);
                        printf("%d\n",j);
                        dict.insert(j);
                        break;
                    }
                }*/
            }
        }
        dict.clear();
    }
    return 0;
}