P3059 [USACO12NOV] Concurrently Balanced Strings G

题目描述

农夫约翰养了一只非常特殊的奶牛品种，以其独特的外貌而闻名，每只奶牛的皮上都有一个巨大的圆形斑点（根据奶牛的朝向不同，这可能看起来像左括号或右括号）。

一天早上，约翰把他的奶牛们分成了 $K$ 行，每行 $N$ 头奶牛（$1 \leq K \leq 10, 1 \leq N \leq 50,000$）。由于奶牛们朝向任意方向，所以这个队列可以用 $K$ 个长度为 $N$ 的括号字符串 $S_1,..., S_k$ 来描述。约翰非常激动地注意到他的牛群中有一些“并发平衡”的范围，其中范围 $i...j$ 的奶牛只有在每个字符串 $S_1,..., S_k$ 在该范围内都是平衡的情况下才能同时平衡（我们将在下面定义单个括号字符串平衡的含义）。例如，如果 $K = 3$ ，我们有

• $S_1 = \texttt{)()((())))(())}$
• $S_2 = \texttt{()(()()()((())}$
• $S_3 = \texttt{)))(()()))(())}$

那么范围 $[3...8]$ 是并发平衡的，因为 $S_1[3...8] = \texttt{((()))}$ ，$S_2[3...8] = \texttt{()()()}$ ，$S_3[3...8] = \texttt{(()())}$ 。范围 $[10...13]$ 和 $[11...12]$ 也是并发平衡的。

给定 $K$ 个长度为 $N$ 的括号字符串，帮助约翰计算范围 $(i,j)$ 的数量，使得范围 $i...j$ 在 $K$ 个字符串中都是并发平衡的。

对于单个括号字符串的“平衡”的定义有几种方式。也许最简单的定义是括号的数量必须相等，并且对于字符串的任何前缀，左括号的数量必须至少和右括号的数量一样多。例如，以下字符串都是平衡的：

• $\texttt{()}$
• $\texttt{(())}$
• $\texttt{()(()())}$

而这些字符串则不是平衡的：

• $\texttt{)(}$
• $\texttt{())(}$
• $\texttt{((())))}$

给出 $K$ 个长度为 $N$ 的括号序列，问有多少个区间在 $K$ 个序列中对应的子串均平衡。

输入格式

第一行：两个整数 $K$ 和 $N$。

第二行至第 $K+1$ 行：每行包含一个长度为 $N$ 的括号字符串。

输出格式

第一行：一个整数，表示并发平衡的范围的数量。

输入输出样例 #1

输入 #1

3 14 
)()((())))(()) 
()(()()()((()) 
)))(()()))(())

输出 #1

3