Matrix.code's blog

By Matrix.code, 10 years ago, In English

The problem is about bracket matching . link

I have solved it. Didn't thought it would pass the time limit . I used segment tree. My update function seems too slow to me, but couldn't think of other way Please Help to optimise

struct dta {
        vector<char> V; // Using vector , stack may be the best
        dta(){}
        dta(char n){V.push_back(n);}
        
}T[3 * MX];


void init( int node , int b , int e)
{
        if(b == e ){
                T[node] = dta(str[b]);
                return;
        }
        int mid = ( b + e ) / 2;
        init(node * 2, b, mid);
        init(node *2 +1 , mid + 1, e);
        T[node].V = T[node *2].V;
        int top = T[node].V.size() - 1;

        // merging the two segments 

        for(int i = 0 ; i< T[node *2+ 1].V.size(); i ++ ){
                if(top>=0 && T[node *2+ 1].V[i] == ')' && T[node].V[top] == '('){
                        T[node].V.pop_back();
                        top -- ;
                }
                else {
                        T[node].V.push_back(T[node *2+ 1].V[i]);
                        top ++;
                }
        }
        
}

void upd ( int node, int b , int e , int pos )
{
        if(b == e ){
                T[node] = dta(str[b]);
                return;
        }
        int mid = ( b + e ) / 2;
        if(pos <= mid ){
                upd(node * 2, b, mid, pos);
        }
        else upd(node *2 +1, mid +1 ,e, pos);
        T[node].V = T[node *2].V;
        int top = (int)T[node].V.size() - 1;
        
        // Update & merge The left & right segment

        for(int i = 0 ; i< T[node *2+ 1].V.size(); i ++ ){
                if(top>=0 && T[node *2+ 1].V[i] == ')' && T[node].V[top] == '('){
                        T[node].V.pop_back();
                        top -- ;
                }
                else {
                        T[node].V.push_back(T[node *2+ 1].V[i]);
                        top ++;
                }
        }
        
        
}

But storing the whole segments and update is too heavy, Don't know the complexity of update operation ( may be n lg n )

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

1 — opening bracket -1 — closing bracket

You need to know the minimal balance on prefix and the sum of all elements. If you need to check the correct bracket sequence, you should check, that the minimal balance in the root = 0 and the sum of all elements = 0. It means, that you need to build segment tree on pref_sums.

My AC code here