SPOJ 61. Brackets Solution

www.spoj.com/problems/BRCKTS/
This is another problem on Segment Trees. Although this is a basic/easy level problem.
In input a string of brackets will be given. The brackets can be open brackets or close brackets. Among these words we will distinguish correct bracket expressions. These are such bracket words in which the brackets can be matched into pairs such that

• every pair consists of an opening bracket and a closing bracket appearing further in the bracket word
• for every pair the part of the word between the brackets of this pair has equal number of opening and closing brackets . 

This means that the string can be of form 1.)  ()()   2.) (())   3.)   ((())) ,etc
But not of the form 1.)  )(  2.)  ))((   3.)  ())(()
If the string is of first form answer will be YES else if of second form answer will be NO.

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 300005

struct DATA{
    int open_brackets;
    int close_brackets;
    DATA(){
        open_brackets=close_brackets = 0;
    }
};

DATA sum[4*MAX];
char str[MAX];

void build_tree(int node, int a, int b){
    if(a>b){
        return;
    }
    if(a==b){
        if(str[a]=='('){      
            sum[node].open_brackets = 1;
            sum[node].close_brackets = 0;
        }
        else{
            sum[node].open_brackets = 0;
            sum[node].close_brackets = 1;
        }
    //    cout<<" sum["<<node<<"] "<<str[node]<<" "<<sum[node].open_brackets<<" "<<sum[node].close_brackets<<" ";
        return;
    }
  
    build_tree(2*node, a, (a+b)/2);
    build_tree((2*node)+1,((a+b)/2)+1, b);
  
    int ol = sum[2*node].open_brackets;
    int cl = sum[2*node].close_brackets;
  
    int orr = sum[2*node+1].open_brackets;
    int crr = sum[2*node+1].close_brackets;
  
    if(ol>=crr){
        sum[node].open_brackets = ol + orr - crr;
    }
    else {
        sum[node].open_brackets = orr;
    }
    if(ol<=crr){
        sum[node].close_brackets = cl+crr-ol;
    }
    else{
        sum[node].close_brackets = cl;
    }
//    cout<<" sum["<<node<<"] "<<str[node]<<" "<<sum[node].open_brackets<<" "<<sum[node].close_brackets<<" ";
}

void update_tree(int node, int a, int b, int val){
    if(a>b){
        return;
    }
  
    if(a==b){
        if(str[val]=='('){
            sum[node].open_brackets--;
            sum[node].close_brackets++;
            str[val] = ')';
        }
        else{
            sum[node].open_brackets++;
            sum[node].close_brackets--;
            str[val] = '(';
        }
        //cout<<str<<endl;
        return;
    }
    if(val <=(a+b)/2){
        update_tree(2*node, a, (a+b)/2,val);
     }
     else{
        update_tree((2*node)+1,((a+b)/2)+1, b,val);
    }
  
    int ol = sum[2*node].open_brackets;
    int cl = sum[2*node].close_brackets;
    int orr = sum[2*node+1].open_brackets;
    int crr = sum[2*node+1].close_brackets;
  
    if(ol>=crr){
        sum[node].open_brackets = ol + orr - crr;
    }
    else {
        sum[node].open_brackets = orr;
    }
    if(ol<=crr){
        sum[node].close_brackets = cl+crr-ol;
    }
    else{
        sum[node].close_brackets = cl;
    }
}
int main() {
    int stlen, m, k;
  
    for(int i = 1; i<=10; i++){
        printf("Test %d:\n",i);
        scanf("%d",&stlen);
        scanf("%s", str);
        stlen--;
        build_tree(1,0,stlen);
        scanf("%d",&m);
        while(m--){
            scanf("%d",&k);
            if(k==0){
                if(str[0]==')'){
                    cout<<"NO\n";
                }
                else{
                //    cout<<sum[1].open_brackets<<" "<<sum[1].close_brackets;
                    if(sum[1].close_brackets==0&&sum[1].open_brackets==0){
                        printf("YES\n");
                    }
                    else{
                        printf("NO\n");
                    }
                }
              
            }
            else{
                update_tree(1,0,stlen,k-1);
            }
        }
    }
    return 0;
}