ACM-ICPC TOKYO 2014 G Flipping Parentheses

  1 // File Name: f.cpp
  2 // Author: darkdream
  3 // Created Time: 2015年03月25日 星期三 13时46分59秒
  4 
  5 #include<vector>
  6 #include<list>
  7 #include<map>
  8 #include<set>
  9 #include<deque>
 10 #include<stack>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<functional>
 14 #include<numeric>
 15 #include<utility>
 16 #include<sstream>
 17 #include<iostream>
 18 #include<iomanip>
 19 #include<cstdio>
 20 #include<cmath>
 21 #include<cstdlib>
 22 #include<cstring>
 23 #include<ctime>
 24 #define LL long long
 25 #define maxn 310005
 26 using namespace std;
 27 char str[maxn];
 28 struct nodd{
 29   int l , r , m ,mi,lazy;
 30 }tree[maxn*4];
 31 int sum[maxn];
 32 int L(int x)
 33 {
 34   return 2 *x; 
 35 }
 36 int R(int x)
 37 {
 38   return 2*x + 1; 
 39 }
 40 void push_up(int c)
 41 {
 42    tree[c].mi = min(tree[L(c)].mi ,tree[R(c)].mi);
 43 }
 44 void push_down(int c)
 45 {
 46   if(tree[c].lazy != 0 )
 47   {
 48    tree[L(c)].mi += tree[c].lazy ; 
 49    tree[R(c)].mi += tree[c].lazy;
 50    tree[L(c)].lazy += tree[c].lazy;
 51    tree[R(c)].lazy += tree[c].lazy ; 
 52    tree[c].lazy = 0 ; 
 53   }
 54 }
 55 void build(int c, int l ,int  r)
 56 {
 57    tree[c].l = l ; 
 58    tree[c].r = r; 
 59    tree[c].m = (l+r)/2;
 60    tree[c].lazy = 0 ; 
 61    if(l == r)
 62    {
 63        //printf("**%d\n",sum[l]);
 64        tree[c].mi = sum[l];
 65        return ;
 66    }
 67    build(L(c),l,tree[c].m);
 68    build(R(c),tree[c].m +1, r);
 69    push_up(c);
 70 }
 71 void update(int c, int l , int r ,int v)
 72 {
 73    if(l <= tree[c].l && r >= tree[c].r)
 74    {
 75       tree[c].mi += v; 
 76       tree[c].lazy += v ;
 77       return ;
 78    }
 79    push_down(c);
 80    if(l <= tree[c].m)
 81        update(L(c),l,r,v);
 82    if(r > tree[c].m)
 83        update(R(c),l,r,v);
 84    push_up(c);
 85 }
 86 int find(int c, int p )
 87 {
 88     //printf("%d %d %d \n",c,tree[c].l,tree[c].r); 
 89     if(tree[c].l == tree[c].r )
 90      {
 91         if(tree[c].mi >= 2)
 92            return tree[c].l; 
 93         return 1e9; 
 94      }
 95      push_down(c);
 96      if(p <= tree[c].m && p >= tree[c].l)
 97      {
 98         return find(L(c),p);
 99      }
100      int t ;
101      //if(tree[c].l == 1)
102     //     printf("***%d\n",tree[R(c)].mi);
103      if(tree[R(c)].mi >= 2)
104          t = tree[c].m + 1;
105      else 
106          t = find(R(c),p);
107      if(t == tree[c].m + 1)
108      {
109          if(tree[L(c)].mi >= 2 ) 
110              return tree[c].l;
111          t = min(t,find(L(c),p));
112     //     printf("***%d %d\n",t,);
113      }else{
114        return t;
115      }
116 }
117 set<int> st;
118 int main(){
119     int n , m;
120     scanf("%d %d",&n,&m);
121     scanf("%s",&str[1]);
122     for(int i = 1;i <= n;i ++)
123     {
124         
125         if(str[i] == ‘)‘)    
126         {
127           st.insert(i);
128           sum[i] = sum[i-1] - 1;
129         }else{
130           sum[i] = sum[i-1] + 1;
131         }
132     }
133     build(1,1,n);
134     int q; 
135     for(int i = 1;i <= m;i ++)
136     {
137        scanf("%d",&q);
138        if(str[q] == ‘(‘)  
139        {
140             str[q] = ‘)‘;    
141             update(1,q,n,-2);
142             st.insert(q);
143             int t = *st.begin();
144             printf("%d\n",t);
145             st.erase(st.find(t));
146             update(1,t,n,2);
147             str[t] = ‘(‘;
148        }else{
149             str[q] = ‘(‘;
150             st.erase(st.find(q));
151             update(1,q,n,2);    
152             int t = find(1,q);
153             update(1,t,n,-2);
154             str[t] = ‘)‘;
155             st.insert(t);
156             printf("%d\n",t);
157        }
158        //puts(&str[1]);
159     }
160 return 0;
161 }