SpojOJ - BRCKTS - Brackets

Problem link: https://www.spoj.com/problems/BRCKTS/

IDEA: This is a simple segment tree problem. All we have to do is find out how to store value in segment tree. As, there are two  types of brackets, we can store them by denoting 1 and -1 respectively. When traversing from leaf node to upper node all we need to calculate sum and left minimum value to ensure this sequence is balanced or not.

CODE: 

#include <bits/stdc++.h>

using namespace std;

int a[30022];
struct node{
    int sum,left;
};
node st[200022];

node nnode(int val)
{
    node x;
    x.sum=val;
    x.left=val;
    //cout<<x.sum<<" "<<x.left<<endl;
    return x;
}

node mergest(node x,node y)
{
    node z;
    z.sum= x.sum+y.sum;
    z.left= min(x.left,x.sum+y.left);
    //cout<<z.sum<<" "<<z.left<<endl;
    return z;
}

void update(int s,int e,int n,int k)
{
    if(s==e)
    {
        if(a[s]==1)
            a[s]=-1;
        else
            a[s]=1;
        st[n]=nnode(a[s]);
        return;
    }
    int mid=(s+e)/2;
    if(k<=mid)
        update(s,mid,n*2,k);
    else
        update(mid+1,e,n*2+1,k);
    st[n]=mergest(st[n*2],st[n*2+1]);
}

void build(int s,int e,int n)
{
    if(s==e)
    {
       st[n]=nnode(a[s]);
       return ;
    }
    int mid=(s+e)/2;
    build(s,mid,n*2);
    build(mid+1,e,n*2+1);
    st[n]=mergest(st[n*2],st[n*2+1]);
}
int main()
{
    int t=10;
    while(t--)
    {
        cout<<"Test "<<10-t<<":"<<endl;
        int n,k;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            char x;
            cin>>x;
            if(x=='(')
                a[i]=1;
            else
                a[i]=-1;
        }
        build(1,n,1);
        //int k;
        cin>>k;
        for(int i=0;i<k;i++)
        {
            int f;
            cin>>f;
            if(f==0)
            {
                if(st[1].sum==0&&st[1].left==0)
                    cout<<"YES"<<endl;
                else
                    cout<<"NO"<<endl;
            }
            else
            {
                update(1,n,1,f);
            }
        }
    }
    return 0;
}