Segment Trees #1 - Segment Trees and Range Queries

CF 223-C Sereja and Brackets

Problem Statement: here

Solution: It is a classical Segment Tree question with no updates.

The only important thing to figure out is what you will be storing in your node.  Like, in this case, we need to think about the possible cases from which we can get the answer when we merge answers from child intervals. 

When we are merging 2 strings, it is true that:

1. The answer for the node is the answer to your child nodes + something.
2.  This something is nothing but the minimum of the number of opening brackets in your left child and number of closing brackets in your right child.

Why are above 2 points true?

1. If suppose we have a string, then we will extract all its proper subsequence brackets. Then, we will be left with only those closing brackets which occur in front of any opening brackets and thus they cannot be combined with any of the opening brackets in the string to get a proper subsequence and similarly for the opening brackets at the end of our string. 
2. So, for each node, we just need 3 integer parameters, that is the answer of your interval, the number of opening brackets after removing the correct brackets, the number of closing brackets after removing the correct brackets.

Implementation : 

ll ans[4000005]={}; ll ob[4000005]={}; ll cb[4000005]={}; string s; ll n; void build(ll ind, ll l, ll r){ if (l == r){ if (s[l] == '('){ ob[ind] = 1; } else cb[ind] = 1; return; } ll mid = (l+r)/2; build(2*ind,l,mid); build(2*ind+1,mid+1,r); ll tmp = min(ob[2*ind],cb[2*ind+1]); ans[ind] = ans[2*ind] + ans[2*ind+1] + tmp; ob[ind] = ob[2*ind] + ob[2*ind+1] - tmp; cb[ind] = cb[2*ind] + cb[2*ind+1] - tmp; } pair<ll,pll> query(ll ind, ll l, ll r, ll qs, ll qe){ if (qs > r || qe < l){ return {0,{0,0}}; } if (qs <= l && qe>= r){ return {ans[ind],{ob[ind],cb[ind]}}; } ll mid = (l+r)/2; pair<ll,pll> left = query(2*ind,l,mid,qs,qe); pair<ll,pll> right = query(2*ind+1,mid+1,r,qs,qe); return {left.F+right.F + min(left.S.F,right.S.S),{ left.S.F + right.S.F - min(left.S.F,right.S.S), left.S.S + right.S.S - min(left.S.F,right.S.S) }}; } void solve() { cin >> s; n = s.size(); build(1,0,n-1); ll m; cin >> m; rep(i,0,m){ ll x,y; cin >> x >> y; pair<ll,pll> val = query(1,0,n-1,x-1,y-1); cout << 2*val.F << endl; } }