Sereja and Brackets

                                Sereja and Brackets

                                  segment tree

Problem Link

#include <iostream>

#include <cmath>

#include <cstring>

using namespace std;

string s;

struct node

{

    long int len; //max length of matched brackets

    int tn, tp; // tp = total number of '(' brackets

                //tn = total number of ')' brackets

};

node func(node a, node b)

{

    node temp;

    int len = min(a.tp, b.tn);

    temp.len = a.len + b.len + 2 * len;

    temp.tp = a.tp + b.tp - len;

    temp.tn = a.tn + b.tn - len;

    return temp;

}

void buildTree(node seg[], int l, int r, int index)

{

    if(l == r)

    {

        seg[index].len = seg[index].tp = seg[index].tn = 0;

        if(s[l] == ')')

        {

            seg[index].tn = 1;

        }

        else

        {

            seg[index].tp = 1;

        }

     }

     else

     {

         int mid = (l + r) / 2;

         buildTree(seg, l, mid, 2 * index + 1);

         buildTree(seg, mid + 1, r, 2 * index + 2);

         seg[index] = func(seg[2 * index + 1], seg[2 * index + 2]);

     }

}

node query(node seg[], int l, int r, int qs, int qe, int index)

{

    if((qs > r || qe < l))

    {

        node temp;

        temp.len = temp.tp = temp.tn = 0;

        return temp;

    }

    else if(qs <= l && qe >= r)

        return seg[index];

    else

    {

        int mid = (l + r ) / 2;

        node p1 = query(seg, l, mid, qs, qe, 2 * index + 1);

        node p2 = query(seg, mid + 1, r, qs, qe, 2 * index + 2);

        node temp = func(p1, p2);

        return temp;

    }

}

int main()

{

    int m, l, r;

    cin >> s;

    long int size = 4 * s.size();

    node seg[size];

    buildTree(seg, 0, s.size() - 1, 0);

    cin >> m;

    while(m--)

    {

        cin >> l >> r;

        node temp = query(seg, 0, s.size() - 1, l - 1, r - 1, 0);

        cout << temp.len << endl;

    }

    return 0;

}