[Codeforces] E. Almost Regular Bracket Sequence

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Almost Regular Bracket Sequence
Source            : Codeforces
Category          : Data Structure
Algorithm         : Segment Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 1e6 + 5;  
  
struct segmentTree  
{  
      int open, close;  
      segmentTree(int open = 0, int close = 0) : open(open), close(close) {}  
  
      void assignLeaf(char bracket)  
      {  
            open = close = 0;  
            if (bracket == '(') ++open;  
            else ++close;  
      }  
      void marge(const segmentTree &lchild, const segmentTree &rchild)  
      {  
            int mini = min(lchild.open, rchild.close);  
            open = lchild.open + rchild.open - mini;  
            close = lchild.close + rchild.close - mini;  
      }  
      bool isRegular()  
      {  
            return (open == 0 && close == 0);  
      }  
} Tree[maxn*4];  
  
int n;  
string s;  
  
void build(int node = 1, int a = 1, int b = n)  
{  
      if (a == b)  
      {  
            Tree[node].assignLeaf(s[a-1]);  
            return;  
      }  
      int lft = node << 1;  
      int rgt = lft | 1;  
      int mid = (a + b) >> 1;  
      build(lft, a, mid);  
      build(rgt, mid+1, b);  
      Tree[node].marge(Tree[lft], Tree[rgt]);  
}  
  
void update(int node, int a, int b, int pos, char bracket)  
{  
      if (a > pos or b < pos) return;  
      if (a >= pos && b <= pos)  
      {  
            Tree[node].assignLeaf(bracket);  
            return;  
      }  
      int lft = node << 1;  
      int rgt = lft | 1;  
      int mid = (a + b) >> 1;  
      update(lft, a, mid, pos, bracket);  
      update(rgt, mid+1, b, pos, bracket);  
      Tree[node].marge(Tree[lft], Tree[rgt]);  
}  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> n >> s;  
      build();  
      int cnt = 0;  
      for (int i = 1; i <= n; i++)  
      {  
            char bracket = s[i-1];  
            if (bracket == '(')  
            {  
                  update(1, 1, n, i, ')');  
                  if (Tree[1].isRegular()) ++cnt;  
                  update(1, 1, n, i, '(');  
            }  
            else  
            {  
                  update(1, 1, n, i, '(');  
                  if (Tree[1].isRegular()) ++cnt;  
                  update(1, 1, n, i, ')');  
            }  
      }  
      cout << cnt;  
}