信息学竞赛中的持久化数据结构与技巧
CF1340F. Nastya and CBS
题目选讲
ARC151E. Keep Being Substring
如果 \(X\) 和 \(Y\) 的最长公共子串的长度 \(L>0\)，那么答案就是 \(P+Q-2L\)。否则，最优方案一定是将 \(X\) 变成单个字符 \(c\)，然后进行若干次在它前面或后面加入一个在原串中和 \(c\) 相邻的字符，再把 \(c\) 删去的操作。当 \(c\in Y\) 时，就可以扩展出 \(Y\) 了。
做多源汇 BFS 即可。时间复杂度 \(O(N)\)。
IOI 2023. Closing Time
称一个点的类型是它能被 \(\{X,Y\}\) 中的几个点到达。设 \(X,Y\) 间路径的点集是 \(S\)。只要整棵树上有一个 \(2\) 类型的点，那么 \(S\) 中的所有点都应当是 \(1,2\) 类型的。
不妨假设树上有至少一个 \(2\) 类型的点。此时，提前钦定 \(S\) 中所有点 \(u\) 都付出了 \(\min(\operatorname{dist}(u,X),\operatorname{dist}(u,Y))\) 的代价。将整棵树分为距离 \(X\) 更近和距离 \(Y\) 更近的两个连通块，此时的问题是：
对于每个点 \(u\)，其可能有一个父亲 \(f_u\)，表示 \(f_u\) 的类型需要大于等于 \(u\) 的类型。\(u\) 选择类型 \(i\) 有一个代价 \(c_{u,i}\)，问在总代价不超过 \(K\) 的情况下，所有点的类型之和最大是多少？
注意到父亲的限制是没有用的，因为原题的条件保证了 \(\forall i,c_{u,i}>c_{f_u,i}\)。于是这个问题就是 Cardboard Box
了。
IOI 2023. Robot Contest
组合计数中的递推问题
无标号组合类的多重集运算
\[\mathscr A=\mathsf{MSet}\ \mathscr B=\prod_{\alpha \in \mathscr B} (\mathsf{Seq}\ \alpha). \]对应的生成函数是
\[A(x)=\prod_{n\ge 1} (1-x^n)^{-[x^n]B(x)}. \]进行一些推导：
\[\begin{aligned} A(x) &=\exp\left(\sum_{n\ge 1} -[x^n]B(x)\ln (1-x^n)\right)\\ &=\exp\left(\sum_{n\ge 1} [x^n]B(x)\sum_{k\ge 1} \frac{x^{nk}}{k}\right)\\ &=\exp\left(\sum_{k\ge 1} \frac{1}{k}\sum_{n\ge 1} [x^n]B(x)x^{nk}\right)\\ &=\exp\left(\sum_{k\ge 1} \frac{B(x^k)}{k}\right) \end{aligned} \]做反演，可以得到
\[B(x)=\sum_{k\ge 1} \frac{\mu(k)}{k} \ln A(x^k). \]假如
\[A=\frac{1}{1-qx}, \]可以通过上面的式子得到 \(\mathscr B\) 的数列。
\(\mathscr A\) 有两种组合意义：
- 字符集大小为 \(q\) 的字符串；
- 有限域上的首一多项式。
对应地，\(\mathscr B\) 也有两种组合意义：
- 字符串的 Lyndon 分解；
- 将多项式分解成若干不可约多项式之积。
微分算子
定义
\[\partial \left(\sum_{n\ge 0} a_nx^n\right)=\sum_{n\ge 1} a_n\cdot nx^{n-1}. \]对于 OGF，有 \(\partial x^n=nx^{n-1}\)；对于 EGF，有 \(\partial \frac{x^n}{n!}=\frac{x^{n-1}}{n-1}\)。
组合意义是，OGF 相当于从一个大小为 \(n\) 的元素中选择一个取出来，将其变成一个大小为 \(n-1\) 的元素；对于 EGF，则是直接将其变成一个大小为 \(n-1\) 的元素。
微分的运算律：
- 可加性：\(\partial(A+B)=\partial A+\partial B\)；
- 乘法：\(\partial(A\cdot B)=(\partial A)\cdot B+A\cdot (\partial B)\)；
- 复合：\(\partial(A\circ B)=((\partial A)\circ B)\cdot \partial B\)。
多重集构造的递推式（有标号）
\[\mathscr B=\mathsf{MSet}\ \mathscr A, \]\[B=\exp A, \]求导，得到
\[B'=B\cdot A', \]提取系数即可得到
\[b_n=\sum_{k=1}^n \binom{n-1}{k-1} a_kb_{n-k}. \tag{22} \]例子：连通图
设 \(\mathscr G\) 是全体无向图的组合类，\(\mathscr C\) 是全体无向连通图的组合类，有 \(\mathscr G=\mathsf{MSet}\ \mathscr C\)。直接代入 \((22)\) 式即可得到一个递推。
假如对 \(G\) 求导，可以得到
\[\begin{aligned} G'(x) &=\sum_{n\ge 0} 2^{\binom{n+1}{2}} \frac{x^n}{n!}\\ &=\sum_{n\ge 0} 2^{\binom{n}{2}} \frac{(2x)^n}{n!}\\ &=G(2x). \end{aligned} \]通过 一些推导，可以得到
\[C''(x)=C'(x)\cdot (2C'(2x)-C'(x)). \]这也导出了 \(\mathscr C\) 的另一种递推式。
例子：\(n\) 王问题
问题：有多少个 \(n\) 阶排列 \(p\) 使得相邻两项之差的绝对值始终不是 \(1\)？设这个数列是 \(A_n\)。
考虑容斥，钦定排列中若干个 \(i\) 一定要满足 \(|p_i-p_{i+1}|=1\)，这将 \(p\) 划分成了若干连续段，每个长度 \(L>1\) 的段带有 \((-1)^{L-1}\) 的容斥系数。
所以一段的带有容斥系数的生成函数就是
\[F(x)=x+2\sum_{i\ge 2} (-1)^{i-2}x^i=x\cdot \frac{1-x}{1+x}. \]由于这些连续段是可以任意排列的，所以这里可以用复合来描述：
\[A(x)=\left(\sum_{n\ge 0} n!x^n\right)\circ F \]记 \(S(x)=\sum_{n\ge 0} n!x^n\)，由于递推式 \(S_n=nS_{n-1}\)，有
\[\begin{aligned} S(x) &=1+\sum_{n\ge 1} (n-1)!\cdot nx^n\\ &=1+x\sum_{n\ge 1} (n-1)!\cdot nx^{n-1}\\ &=1+x\cdot (x\cdot S(x))'\\ &=1+xS(x)+x^2S'(x). \end{aligned} \]所以有
\[A=1+FA+F^2S'(F). \]\(S'(F)\) 不好处理，考虑逆用求导的复合公式：
\[(\partial A)\circ B=\frac{\partial (A\circ B)}{\partial B}, \]所以
\[A=1+FA+\frac{F^2A'}{F'}. \]这样就导出了 \(A_n\) 的递推式。
思考：2-正则图
记 \(\mathscr A\) 是 2-正则图的组合类，求其 EGF \(A(x)\)。
记 \(\mathscr C\) 是简单环的组合类，有 \(\mathscr A=\mathsf{MSet}\ \mathscr C\)。
\[\begin{aligned} C(x) &=\sum_{n\ge 3} \frac{(n-1)!}{2}\cdot \frac{x^n}{n!}\\ &=\frac{1}{2}\cdot \sum_{n\ge 3} \frac{x^n}{n}\\ &=\frac{1}{2}\left(-\ln(1-x)-x-\frac{x^2}{2}\right). \end{aligned} \]于是
\[\begin{aligned} A(x) &=\exp C(x)\\ &=\exp\left(\frac{1}{2}(-\ln(1-x)-x-\frac{x^2}{2})\right)\\ &=\exp\left(-\ln\sqrt{1-x}-\frac{x}{2}-\frac{x^2}{4}\right)\\ &=\left(\sqrt{1-x}\right)^{-1}\exp\left(-\frac{x}{2}-\frac{x^2}{4}\right). \end{aligned} \]杂题选讲
IOI 2023. Longest Trip
IOI 2023. Soccer Stadium
CF1175G. Yet Another Partiton Problem
暴力自然是设 \(f_{i,j}\) 表示将 \(a_1,a_2,\dots,a_j\) 划分成 \(i\) 段的最小代价。由于 \(f_i\) 和 \(f_{i+1}\) 之间的转移形如
\[F_i=\min_{0\le j<i} \{G_j+(i-j)\cdot \max_{j<k\le i} \{a_k\}\}, \]考虑 CDQ 分治来做这个东西。假如现在要算 \([l,m]\) 对 \((m,r]\) 的贡献，那么式子中的 \(\max\) 可以分取在 \([l,m]\) 和取在 \((m,r]\) 两类讨论，而这两类都是斜率优化。时间复杂度 \(O(nk\log n)\)。
关于斜率优化：
- 形如 \(f=\min_{(x,y)\in S}\{y-kx\}\) 的式子可以看作，最小化过 \((x,y)\) 且斜率为 \(k\) 的直线在 \(y\) 轴上的截距；
- 注意特判两个点横坐标相同的情况。