括号问题

Published: December 07, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 括号序列数目统计
• 限制匹配的括号序列问题
• 最短合法括号子串
• 统计合法的括号子串数
• 括号树
• 完美匹配问题

括号序列数目统计

题目1：计算长度为$n$的有效括号序列数目，结果对素数取模。

Catalan数的基本应用。

$${2n\choose n} - {2n \choose n + 1}$$

题目2：给定长度为$n$的一段括号序列$S$，记$m$为最短的有效括号序列的长度，满足$S$是$T$的子序列（不要求连续）。问长度为$m$的包含$S$作为子序列的有效括号序列数目（相同序列只计数一次），结果对素数取模。其中$1\leq n\leq 5000$。

我们将左括号看作1，右括号看成-1，而最小前缀和为$w$，记出现的下标位置为$x$。序列$S$的总和为$s$。那么很显然我们至少要插入$-w$个左括号，对应的至少需要右括号$s-w$个。

现在我们考虑如何计算有效数目，我们可以令$dp(i,j,k)$表示考虑前$i$个字符，当前和为$j$，贪心匹配$S$的前$k$个字符的方案数。这个动态规划的时间复杂度为$O(n^3)$。

但是考虑到我们仅插入了最少的字符，所以实际上还可以进一步优化。我们可以认为当前有$n+1$个空槽（由原字符串分隔）可以允许插入，具体的思路如下:

• 同一个空隙中不会同时插入1和-1（否则我们同时删除一个1和-1可以得到更短的有效括号序列）
• 插入的1一定出现在插入的-1之前

上面的过程实际上已经给出了一个$O(n^2)$的算法。具体就是记$dp(i,j,k)$表示考虑前$i$个空槽，前缀和为$j$，$k$表示上一次插入的字符为-1还是1。

当然这个算法没有考虑去重的问题，一个很简单的去重思路就是只有在前一个字符不是左括号的时候才允许插入左括号，同理后一个字符不是右括号的时候才允许插入右括号。很显然这样得到的序列是不会重复的。

并且实际上，如果$i\leq x$的时候，很显然只可能插入左括号，而$i> x$的时候，此时只能插入右括号。因此我们可以把$k$去掉，用$dp(i,j)$表示仅考虑前$i$个空槽，前缀和为$j$的方案数。

限制匹配的括号序列问题

题目1：长度为$n$的01字符串$s$有多少，满足存在一个与$s$等长的合法的括号序列，如果$i$和$j$匹配，则必须$s_i=s_j$。

首先$n$如果是奇数，那么结果一定是$0$，接下来我们假定$n$是偶数。

考虑由$0$占领的下标，记录$a$为其中奇数的数目，$b$为其中偶数的数目。可以发现如果$a\neq b$，则必定会出现相同奇偶性下标配对的情况（此时其中留给方括号的长度为奇数），这时候是不可能产生合法的交错括号序列的。因此$a=b$是有解的前提。

接下来我们说明如果$a=b$一定有解。实际上我们可以不断找到两个相邻的0出现的下标（忽略1出现的位置），其中一者是偶数，另外一者是奇数。之后我们将它们配对，并删除。重复这个过程我们就可以将$0$替换为圆括号。之后对$1$的替换就非常简单了。

因此答案为$\sum_{i=0}^{n/2} {n/2\choose i}^2$。

题目2：给定长度为$n$的序列$a$和序列$b$，之后要求找到一组权值最大的一个长度为$n$的01字符串$s$，满足存在一个与$s$等长的合法的括号序列，如果$i$和$j$匹配，则必须$s_i=s_j$。其中$n$为偶数。

首先我们可以将所有位置都放置为方括号，之后我们考虑将一些位置替换为圆括号，我们定义$c_i=a_i-b_i$。

在题目1中我们已经讨论过圆括号中奇数下标和偶数下标数量相同是存在一种方案的等价条件。因此我们可以不断找到权重$c$最大的奇数下标和偶数下标$i,j$，如果$c_i+c_j\gt 0$，则将这两个下标替换为圆括号并重复流程，否则退出流程。

提供一道题目。

题目3：给定长度为$n$的字符串$s$，判断是否存在一个与$s$等长的合法括号序列，如果$i$和$j$匹配，则必须$s_i=s_j$。

这个问题可以用贪心算法求解。如果存在两个相同的字符相邻，那么可以同时让它们匹配并消除它。可以证明如果存在可行解，那么这个过程一定能得到一个合法的交错括号序列。

我们可以遍历$s$，并维护一个栈，每次遇到相同元素的时候就弹出，否则入栈。如果最后栈为空，则由解，否则无解。这个算法的时间复杂度为$O(n)$。

题目4：要求维护字符串$s$，初始为空。之后回答$q$个请求，请求分四类：

• 头部插入一个字符
• 尾部插入一个字符
• 头部删除一个字符
• 尾部删除一个字符

要求每次操作后，判断是否存在一个与$s$等长的合法括号序列，如果$i$和$j$匹配，则必须$s_i=s_j$。

类似题目3，我们可以维护一个双端栈支持插入操作。由于对于任意$c$，有$2c=0$，所以删除一个字符等价于插入一个字符。而存在可行解等价于最终栈为空。总的时间复杂度为$O(q)$。

题目5：给定长度为$n$的字符串$s$，之后处理$q$个请求。每个请求指定一段区间，问区间代表的字符串$t$，是否存在一个与$t$等长的合法括号序列，如果$i$和$j$匹配，则必须$t_i=t_j$。其中$1\leq n,q\leq 10^6$。

第一种做法。

根据题目4的做法，我们可以发现很容易支持两端的插入和删除。那么我们就可以很自然的使用莫队来解决这个问题，时间复杂度为$O(q\sqrt{n})$。

第二种做法。

令$L_i$表示处理前$i$个字符得到的栈状态。那么现在我们希望判断$l,r$之间的字符串处理后栈是否为空，这等价于$L_{l-1}=L_r$。我们可以利用哈希快速判断是否相等。

这种做法的时间复杂度为$O(n+q)$。

题目6：给定长度为$n$的字符串$s$，问区间代表的字符串$s$，是否存在一个与$s$等长的合法括号序列，如果$i$和$j$匹配，则必须$s_i=s_j$。如果无解，则报告，否则找到所有满足条件的括号序列中字典序最小的（认为左括号小于右括号）。

提供一道题目。

可以用题目3的做法判断是否有解。无解则结束。

否则我们考虑贪心算法，考虑第一个字符，以及考虑所有可能与其匹配的字符，很显然它一定会匹配最右的那个位置（否则我们可以翻转它原来匹配的位置得到更优的一个结果）。

现在考虑我们设计了一个函数$solve(l,r)$，它会根据l,r之间的所有字符构造一个完整的合法括号序列，有多个就取字典序最小的那个。那么我们可以先找到所有能与$l$匹配的最右位置$x$（$l<x\leq r$）。那么现在的问题变成如何找到这个$x$。

如果一段区间l~r可以形成合法的括号序列，则一定有$stack(l-1)=stack(r)$，其中$stack(i)$表示仅考虑前i个位置形成的问题3中的栈。我们可以利用哈希来找到所有相同的位置并维护在平衡树上，之后我们只需要找到哈希值为$stack(l)$且位置值为$s_l$的所有位置中，不超过$r$的最大值，这就是$x$。

最短合法括号子串

题目1：给定一个长度为$n$的括号序列，之后对于$i=1,\ldots,n$，分别找出以第$i$个字符开始最短的非空合法括号序列的长度，如果不存在则输出$-1$。

我们可以记R[i]表示以$i$开始最短非空合法括号序列的结束位置，则我们在处理R[i]的时候可以先将其设置为$i+1$，之后检查s[R[i]]是否是)，如果不是，则将R[i]设置为R[R[i]]+1。重复这个操作即可。这是因为，如果一个括号序列不是()，则一定内部包含若干个不相交的合法括号子序列。

上面的过程的时间复杂度是$O(n)$。

统计合法的括号子串数

题目1：给定一个长度为$n$的括号序列，要求计算其中有多少非空子字符串（连续的），是一个合法的括号序列。

首先我们求出R[i]，表示以$i$开始最短非空合法括号序列的结束位置。可以发现这时候如果我们将$i$的父亲设置为$R[i]+1$，那么可以发现这时候形成了一棵树，且树上某个顶点到其任意祖先的路径上的顶点序列对应一个合法的括号子串。因此答案为每个顶点的深度之和。

时间复杂度为$O(n)$。

题目2：在题目1的基础上。要求将结果去重，即两个不同的子串，其值相同，那么只需要统计一次。

一般统计字符串不同子串需要用到lcp或后缀自动机，而统计不同回文需要用到回文自动机。这边统计不同的合法括号子串，则也需要类似的方式来去重。

首先我们在题目1的基础上，构建出最终的树。之后我们考虑如何去重。我们可以通过SA算法求出lcp数组。之后为了保证仅统计一次，对应公共的子串，我们仅在处理较大后缀的时候计算一次。这时候就相当于询问在$right[j]>x$且满足$j$是顶点$i$的祖先的有多少个。这里可以使用倍增或持久化线段树来做。

这里时间复杂度和空间复杂度为$O(n\log_2n)$。

括号树

名字瞎起的。考虑给定一个长度为$n$的有效的括号序列$S$，其中可能有$O(n^2)$个有效括号子串，但是如果我们仅考虑那些不能分割为多个括号子串的那些有效括号子串，称它们为本原串，那么很显然这时候只有$O(n)$个本原串（每个左括号唯一确定一个本原串）。

之后我们可以发现本原串之间只有不相交和包含两种关系。这很类似树，我们可以建立一颗括号树，每个结点对应一个本原串，结点的父亲是最小的本原串，包含结点代表的本原串。可以发现每个字符正好是一个结点的一个端点，不同的结点端点不相交。很显然得到的树的大小为$n/2$。

如果给定的串不是有效的括号序列，我们可以在前面插入一些左括号，右边插入一些右括号，来保证它是有效的括号序列，很显然新的括号序列的长度不超过$2n$。为了方便起见，我们在左边额外插入一个左括号，右边额外插入一个右括号，这样可以保证最后构建出来的树只有一个根。

实际上这东西很类似析合树。它也有很多很好的性质：

• 括号树的大小是$O(n)$的
• 每个有效括号序列，要么是一个本原串（对应一个结点），要么是多个连续的本原串的并（对应某个结点下的连续孩子）

接下来这东西可以解决很多问题。比方说，选定一段区间$[l,r]$，要求找到区间中最长的连续子串的长度（如果不存在则输出$0$）。

这个问题如何解决。我们可以找到$l-1$所属的端点front和$r+1$所属的端点back。那么front到back这条路径上的所有结点都不能被考虑。而由front到back路径下方的所有结点都是可以被考虑的。我们可以为每个结点$u$维护一个L_u和$R_u$属性，分别表示所有$u$左边和右边的兄弟结点的摘要。之后通过倍增技术就能快速的找到路径下方的所有结点的摘要。在这里括号树和析合树有一些区别，在析合树种front和back一定是叶子，而括号树中是不能保证这个性质的，因此需要特殊处理。如果l-1是front的左端点，我们需要额外计算front所有孩子的摘要，同理如果是r+1是back的右端点，我们也需要额外计算back所有孩子的摘要。这个过程我们可以通过树上倍增实现，时间复杂度为$O(\log_2n)$。

我们把之前问题中的长度换成区间中有多少有效的括号子串，可以通过相同方法计算。

现在考虑另外一个问题：给定一段区间$[l,r]$，要求找到另外一段区间$[L,R]$，其中$L\leq l\leq r\leq R$，且$S[L..R]$是一个有效括号序列，且$R-L$最小。

我们可以找到$l$所属端点front和$r$所属端点back，记它们的lca为top。那么如果front或back是top的时候，最短的有效括号序列为top对应的本原端。否则找到top孩子中front和back的祖先，它们之间的所有结点对应的有效括号序列就是答案。时间复杂度为$O(\log_2n)$。

再考虑一个更简单的问题：给定一个下标$i$，要求找到包含下标$i$的最短的一个有效括号序列。

我们可以直接找到以$i$为端点的本原串，这就是答案了。

提供一些题目：

• bzoj4964 加长的咒语

完美匹配问题

题目1：给定一个长度为$n$的括号序列，一个左括号可以和出现在它右边的右括号匹配。一组匹配是合法的，当且仅当没有交错的括号对。判断是否存在完美匹配，如果有则找到一组。

从左到右扫描所有的字符，维护所有未匹配的左括号，记左括号的集合为$L$。

如果遇到一个右括号，那么它只能匹配$L$中下标最大的下标的左括号（否则一定会发生交错）。

所以上面的过程就给出了$O(n)$的算法。

题目2：在二维平面，给定$n$个左括号和$n$个右括号（位置两两不同）。一个左括号可以和它右上方的任意一个右括号匹配。一组匹配是合法的，当且仅当匹配括号对围成的矩形外轮廓没有接触关系。判断是否存在完美匹配，如果有则找到一组。

提供一道题目。

我们将所有点按照$x$作为第一关键字，$y$作为第二关键字进行排序。之后顺序处理顶点，并且维护所有未匹配左括号。如果遇到一个右括号，则找到所有未匹配左括号中$y$坐标最大的一个进行匹配（否则一定会相交）。

注意上面的流程只能保证在存在完美匹配的时候，一定是我们找到的匹配，即完美匹配是唯一的。如果不存在完美匹配，那么上面这个流程要么无法找到最大匹配，要么找到的最大匹配是非法的。

现在的问题是判断有若干个矩形，判断矩形的边界是否有接触。这个实际上就是给定若干条垂直和水平的线段，问是否有交点。这个可以用线段树处理。

总的时间复杂度为$O(n\log_2n)$。