题解：P6020 [Ynoi2010] Exponential tree

· · 题解

P6020 [Ynoi2010] Exponential tree / P8984 [北大集训 2021] 末日魔法少女计划

一个题。爱来自 lxl 讲课。

首先，你发现你这个矩阵的结构很像一个数据结构的查询过程。具体的，限制解析如下：

我们考虑朴素的 $k = 2$，此时的限制很宽松，差不多允许 $n \log n$ 级别的预处理数量，此时每个区间可以被两个区间合成，这很像我们的猫树分治结构（事实上，猫树分治又名“二区间合并”，即任意区间信息可以被最多 $2$ 个区间合并生成）。 这里不能使用 Sparse Table（即 ST 表）的原因是，ST 的合并会有重叠部分，ST 使用的要求是重叠部分不影响合并后结果（如著名的 RMQ 问题，由于区间最值的重叠部分不影响结果，所以 ST 表是可行的），而这里显然是会影响的。 考虑 $k = 3$，此时我们的余量变成了 $n \log \log n$ 量级。我们尝试在猫树结构上分块，预处理所有的从 $l$ 块开头到 $r$ 块结尾类型的贡献，块内处理前后缀，此时预处理的信息量 $O(n)$ 且我们对于跨块贡献显然可以最多三个块解决问题。 你可能认为我们赢了但其实还没有，此时问题在于块内，块内我们当然不能暴力处理否则我们的复杂度是 $nB$ 的。我们尝试在块内继续向下推，形成树形结构，由于每层 $O(n)$，所以只需要证明层数 $\log \log$ 即可。（事实上，这个结构称为 Sqrt Tree） 稍微证明一下层数：设 $n = 2^k$，则 $\sqrt n = 2^{\frac{k}{2}}，\sqrt{\sqrt{n}} = 2^\frac{k}{4}, \cdots$，于是层数是 $\log k$ 的，而 $k = \log n$，所以层数 $\log \log n$ 的。 接下来考虑推广。不妨猜测后面的做法都是构造 Sqrt Tree 结构，我们发现 $k = 3$ 中每一层干的事情都是预处理块内前后缀，块间信息变成了一个 $k - 2$ 次的子问题，对每个块块内向下递归处理规模更小的 $k$ 次的子问题。 那么我们考虑 dp 出最优解，设计状态为 $dp_{i, k}$ 表示区间长度 $i$，$k$ 次合并出结果的最小代价，那么答案就是 $dp_{n, k}$。 我们干的事情相当于是对这个区间分块。枚举块数为 $x$，$i \bmod x = t$，转移式子写出来就是 $dp_{i, k} = \min t \times dp_{\lceil \frac{n}{x} \rceil, k - 2} + (x - t) \times dp_{\lfloor \frac{n}{x} \rfloor, k - 2} + dp_{x, k} + c_{i, k}$ 其中 $c_{i, k}$ 是你预处理块内前后缀的部分产生的贡献。方案是好构造的，预处理转移点，对于每层很容易写出预处理方式。注意 $c$ 的处理有一定的卡常需要，以及 dp 的一些 corner。 另外有一种做法是刻画成一张图，有任意两点最长路的限制。 （这个 dp 的理论价值远大于实践价值，各种 dp 本质类似，实现建议写别的 dp） （我写了一上午死活写不对 corner/ll）