P7604 [THUPC2021] 形式语言与自动机

· · 题解

这里是出题人为喜欢线性做法的选手提供的其中一种将复杂度优化到线性的算法。

令 f(t)=\sum_{i=1}^{|t|}1-(2\times[t_i=\text{)}])，也就是 t 串中左括号减去右括号的数量。

一个串 t 是合法的括号序列当且仅当其每个前缀对应的 f 都非负，且整个串 f(t)=0。

一个 key thought 就是把 $uwv$ 分为 $uw$ 的前缀和 $v$ 这个后缀分别考虑，基于一个显然的事实是 $f(uwv)=0$，若 $uw$ 为合法前缀且 $v$ 为合法后缀，则 $uwv$ 为合法括号序。 转化为如下限制： - $u$ 为合法前缀，要求 $\forall i\le|u|,f(u_i)\ge 0$。 - $v$ 为合法后缀，要求 $\forall i\le|v|,f(v_{|v|})-f(v_{i})\le 0$。 - $uw$ 为合法前缀，要求 $\forall i\le|w|,f(u_{|u|})+f(w_i)\ge 0$。 令 $S(i)=f(s_i)$，即特指给定串 $s$ 的前缀和，$l=|u|,r=|u|+|v|$，即在 $l,r$ 处划分 $u,v,w$ 串，这里与题目定义相同。 以上限制可以用 $S,l,r$ 来表示： - 题目定义：$0\le l<r<n$。 - $u$ 为合法前缀，要求 $\forall i\le l,S(i)\ge 0$。 - $v$ 为合法后缀，要求 $\forall l<i\le r,S(r)\le S(i)$。 - $uw$ 为合法前缀，要求 $\forall r<i,S(l)+S(i)-S(r)\ge 0$。 题目定义为第零个限制，第一个限制是简单的，第二个限制与 $l$ 的位置有关，第三个限制与 $S(l)$ 有关。 先处理第三个限制，令 $d(r)=\min_{i>r} S(i)-S(r)$，则第三个限制转化为 $S(l)+d(r)\ge 0$，即 $S(l)\ge -d(r)$。 考虑对每个 $r$ 计数有多少个 $l$ 合法，前三个限制都只与位置有关，如果直接当做偏序限制使用二维数点，~~虽然被出题人放过了~~，显然没有利用到限制本身的优秀性质。 考虑依次加入点 $(i,S(i))$，在加入 $i$ 前计数 $0\sim i-1$ 作为 $l$ 对 $r=i$ 的贡献，这样满足了第零个限制。 记录一个变量 $flag=\prod_i[S(i)\ge 0]$，作为加入每个点的贡献，这样就满足了第一个限制。 重要的是第二个限制，考虑维护一条条的分支链，分支链的每个位置代表贡献限制相同的点 $\{(x,S(x))\}$ 的集合。 实际上我们并不关心集合里有哪些点，故只需记录其大小，由于第三个限制，故每个位置的 $S$ 相同。 故每个位置可以用一个二元组 $(S,\{S\})$，表示其 $S$ 与集合大小，来代表这个位置，对限制的满足还体现在它位于哪个分支链上，实际上它在分支链的位置上具体是按其 $S$ 顺序连接的，这样是方便处理限制三的询问的。 每条分支链的起点的 $S=\min_{l<i\le r}S(i)$，满足了第二个限制，这样就满足了所有限制，我们只需要对分支链位置的集合大小做一个后缀和，就可以快速回答第三个限制的询问了。 以下是对算法流程的描述：考虑由 $i-1\to i$ 分支链的变化，如果 $S\to S+1$，那么上一个维护的分支链被留在了起点为 $(i-1,S(i-1))$ 所属集合的位置，此时相当于在**预构一条新的分支链**。 如果 $S\to S-1$，那么当前的分支链就**处于构建的状态**，也就是正在变长，起点正在前移，我们只需维护后缀和即可，如果 $S-1$ 那里有以前的一条分支链，我们需要支持将当前的分支链合并到以前的分支链上。 为了做到线性，对于留下上一条分支链和预构新分支链，以及合并到上一条分支链**都不应与上一条分支链的大小有关**，我们需要 $O(1)$ 实现。 同时预构新分支链和合并分支链**都应该只与当前分支链的大小有关**，这样才能进行势能分析，最后总复杂度 $O(n)$。 放了完整的[代码](https://www.luogu.com.cn/paste/qdl4387p)，方便对拍，但算法流程讲了就没写注释，看不懂可以直接询问。 实现细节：对于初状态，我们可以放一条 $(S=0,\{S\}=1),(S=1,\{S\}=0)$ 的分支链。 如果怕挂可以先放一条 $(S=0,\{S\}=1),(S=1,\{S\}=0),(S=2,\{S\}=0),\cdots,(S=n,\{S\}=0)$ 的分支链，然后再改回来。（实际不一定能避免什么可能挂的地方，而且不改回来常数加倍） 维护了后缀和后，为了处理询问，我们应维护出分支链的终点，注意到其构建变长的过程中变化的是起点，故终点不变，只用在合并时处理即可。