题目链接：
首先我们不考虑本质不同这个限制。
既然不能直接用栈乱搞，我们就可以用一个前缀和的套路了。
我们将(设为1，将)设为-1，记前缀和为$s_i$，则$[i,j]$这一段是回文子串当且仅当
1.$s_j=s_{i-1}$
2.$\forall k\in [i,j],s_k\geq s_{i-1}$
于是我们枚举$i$，显然$j$要满足第二个性质就肯定不能超过一个上界，这个上界是可以二分的。每次check的时候就判断一下区间最小值，可以用ST表维护。
然后看看本质不同如何做。
这时候我们就要请出SA，求出$sa[]$和$ht[]$之后，枚举$sa[i]$作为左端点，此时必须$j\geq sa[i]+ht[i]$，其中$ht[]$是高度数组，否则就会与前面的字符串重复。
改一改二分的区间就可以了。
1 #include2 #define Rint register int 3 using namespace std; 4 typedef long long LL; 5 const int N = 500003; 6 int n, a[N], m, sa[N], rak[N], tmp[N], c[N], *x = rak, *y = tmp, ht[N]; 7 LL ans; 8 inline void Qsort(){ 9 for(Rint i = 1;i <= m;i ++) c[i] = 0;10 for(Rint i = 1;i <= n;i ++) ++ c[x[y[i]]];11 for(Rint i = 1;i <= m;i ++) c[i] += c[i - 1];12 for(Rint i = n;i;i --) sa[c[x[y[i]]] --] = y[i];13 }14 inline void Ssort(){15 m = 2;16 for(Rint i = 1;i <= n;i ++){17 x[i] = a[i]; y[i] = i;18 }19 Qsort();20 for(Rint w = 1, p;w < n;w <<= 1, m = p){21 p = 0;22 for(Rint i = n - w + 1;i <= n;i ++) y[++ p] = i;23 for(Rint i = 1;i <= n;i ++) if(sa[i] > w) y[++ p] = sa[i] - w;24 Qsort();25 swap(x, y);26 x[sa[1]] = p = 1;27 for(Rint i = 2;i <= n;i ++)28 x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + w] == y[sa[i - 1] + w]) ? p : ++ p;29 if(p >= n) break; 30 }31 for(Rint i = 1;i <= n;i ++) rak[sa[i]] = i;32 int k = 0;33 for(Rint i = 1;i <= n;i ++){34 if(rak[i] == 1) continue;35 int j = sa[rak[i] - 1];36 if(k) -- k;37 while(a[j + k] == a[i + k]) ++ k;38 ht[rak[i]] = k;39 }40 }41 int st[20][N], lg2[N];42 inline int query(int l, int r){43 int k = lg2[r - l + 1];44 return min(st[k][l], st[k][r - (1 << k) + 1]);45 }46 vector pos[N << 1];47 int main(){48 scanf("%d", &n);49 for(Rint i = 1;i <= n;i ++){50 int ch = getchar();51 while(ch != '(' && ch != ')') ch = getchar();52 a[i] = (ch == ')') + 1;53 }54 Ssort();55 st[0][0] = n;56 for(Rint i = 1;i <= n;i ++) st[0][i] = st[0][i - 1] - a[i] * 2 + 3;57 for(Rint i = 1;i <= n;i ++) pos[st[0][i]].push_back(i);58 for(Rint i = 1;i <= 19;i ++)59 for(Rint j = 1;j <= n;j ++)60 st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);61 lg2[1] = 0;62 for(Rint i = 2;i <= n;i ++) lg2[i] = lg2[i >> 1] + 1;63 for(Rint i = 1;i <= n;i ++){64 if(a[sa[i]] == 2) continue;65 int l = sa[i] + ht[i], r = n, mid, res = l - 1;66 while(l <= r){67 mid = l + r >> 1;68 if(query(sa[i], mid) >= st[0][sa[i] - 1]){l = mid + 1, res = mid;}69 else r = mid - 1;70 }71 int t = st[0][sa[i] - 1];72 ans += upper_bound(pos[t].begin(), pos[t].end(), res) - lower_bound(pos[t].begin(), pos[t].end(), sa[i] + ht[i]);73 }74 printf("%I64d\n", ans);75 }76 // nantf tai qiang le