653F - Paper task - CodeForces Solution

#include<algorithm>
#include<cstdio>
#include<vector>
#define ll long long
#define pb push_back
#define MaxN 500500
using namespace std;
struct Node
{int t[2],f,len,ed;}
a[MaxN<<1];
int tn,las;
void add(int c)
{
  int p=las,np=++tn;las=np;
  a[np].len=a[p].len+1;
  for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
  if (!p)a[np].f=1;
  else {
    int v=a[p].t[c];
    if (a[v].len==a[p].len+1)a[np].f=v;
    else {
      int nv=++tn;a[nv]=a[v];
      a[nv].len=a[p].len+1;
      for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
      a[np].f=a[v].f=nv;
    }
  }
}
vector<int> p[MaxN<<1],g[MaxN<<1];
int n,t[20][MaxN],lg2[MaxN],s[MaxN];
int qry(int l,int r){
  int k=lg2[r-l+1];
  return min(t[k][l],t[k][r-(1<<k)+1]);
}
ll ans=0;
void dfs(int u)
{
  for (int i=0;i<g[u].size();i++){
    dfs(g[u][i]);
    a[u].ed=a[g[u][i]].ed;
  }
  int ed=a[u].ed,
      l=ed-a[u].len+1,sr=ed-a[a[u].f].len,mid,r=sr+1;
  while(l<r){
    mid=(l+r)>>1;
    if (qry(mid,ed)>=s[ed+1])r=mid;
    else l=mid+1;
  }
  ans+=
    upper_bound(p[n+s[ed+1]].begin(),p[n+s[ed+1]].end(),sr)-
    lower_bound(p[n+s[ed+1]].begin(),p[n+s[ed+1]].end(),r)
  ;
}
char str[MaxN];
int main()
{
  scanf("%d%s",&n,str+1);
  for (int i=n;i;i--)
    t[0][i]=s[i]=s[i+1]+((str[i]=='(' ? -1 : 1));
  for (int i=1;i<=n+1;i++)
    p[n+s[i]].pb(i);
  for (int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
  for (int j=1;(1<<j)<=n;j++)
    for (int i=1;i<=n;i++)
      t[j][i]=min(t[j-1][i],t[j-1][i+(1<<j-1)]);
  las=tn=1;
  for (int i=1;i<=n;i++)add(str[i]-'(');
  for (int i=1,p=1;i<=n;i++)
  	a[p=a[p].t[str[i]-'(']].ed=i;
  for (int i=2;i<=tn;i++)g[a[i].f].pb(i);
  dfs(1);
  printf("%lld\n",ans);
  return 0;
}