WGOI R1 真夏飞焰 题解.18014664

【题目大意】

给定序列 \(a\)，我们定义序列 \(a,b\) 是「\(k\) 相似」的，当且仅当对于 \(a\) 中每一个四元组 \((l_1,r_1,l_2,r_2)\)，若满足 \(r_1 - l_1 + 1 = r_2 - l_2 + 1 \le k,l_2 = r_1 + 1,a_{l_1\ldots r_1} = a_{l_2 \ldots r_2}\)，则有 \(b_{l_1\ldots r_1} = b_{l_2 \ldots r_2}\)。

给出 \(n\) 个限制形如 \(b_i \in [L_i,R_i]\)，对 \(k \in [1,\dfrac{n}{2}]\) 求出：如果序列 \(a,b\) 是 「\(k\) 相似」的，有多少种合法的序列 \(b\)，对 \(998244353\) 取模。

\(1 \le n \le 10^6,1 \le L_i \le R_i \le 10^6\)。

【题解】

WGOI 指 五哥 OI（雾

考虑朴素暴力：用并查集维护 \(b\) 的相等关系，同一个连通块内 \(b\) 相等，因此我们可以把 \(L\) 取 \(\max\)，\(R\) 取 \(\min\)，最终答案是所有连通块的 \(R-L+1\) 之积。枚举 \(l_1,l_2\)，如果有 \(a_{l_1\ldots r_1} = a_{l_2 \ldots r_2}\)，则对于 \(j \in [l_1,r_1]\)，合并 \(j,j+r_1-l_1\)。判断相等可以用 SA，时间复杂度 \(\mathcal O(n^3 \log n)\)，期望得分 \(10\) 分。

有一个简单优化：注意到只有 \(\mathcal O(n^2)\) 对不同的 \((i,j)\)，我们对于一次区间合并操作，可以差分，最后再扫一遍一起合并，时间复杂度 \(\mathcal O(n^2 \log n)\)，期望得分 \(20\) 分，但是实测如果实现精良可以得 \(40\) 分。

上面的做法有两个瓶颈：一是找到所有区间 \([i,j]\) 需要 \(\mathcal O(n^2)\) 的时间，二是合并区间需要 \(\mathcal O(n^2 \log n)\) 的时间。我们分开解决。

第一部分是套路的，其实就是找所有形如 \(\text{AA}\) 的串。用 NOI2016 优秀的拆分 的套路，对于 \(\text{|A|} = i\)，在 \(j = i,2i,\ldots,ki\) 设置关键点，一个形如 \(\text{AA}\) 的串会恰好跨过两个关键点。我们枚举相邻的关键点 \(p,q\)，求后缀 \(p,q\) 的最长公共前缀 \(d_1\) 和前缀 \(p,q\) 的最长公共后缀 \(d_2\)，如果 \(d_1 + d_2 - 1 \ge i\)，可以得到一个长度为 \(\mathcal O(i)\) 的合并区间。由调和级数，枚举关键点的复杂度为 \(\mathcal O(n \log n)\)，求最长公共前后缀可以 SA \(\mathcal O(1)\) 回答。

事实上，如果你写到这里就直接提交，由于数据很强，可以获得 \(100\) 分，但是我们的复杂度还是 \(\mathcal O(n^2 \log n)\)，用一个全 \(\texttt{a}\) 串即可卡满。

注意到只有 \(\mathcal O(n)\) 个点，即只有 \(\mathcal O(n)\) 次有用的合并，我们希望快速找到它们。