日记

Wed Mar 19 2025

3 分钟

456 字

虽然排名没长进，但是分数有长进啊。

我都能一眼，当然不用说了。

经过一番推导，我们发现 $f(n,i) = (i + 1)^n$ ，从而有 $f(f(n,i)) = (i + 1)^{(i + 1)^n}$ 。直接欧拉定理 + 快速幂。

首先，我们有结论：如果线段 $L_1$ 包含了 $L_2$ ，那么 $L_1$ 要么单独成组，要么和 $L_2$ 分到一组。

证明：如果 $L_1$ 和 $L_3$ 分成了一组， $L_2$ 和 $L_4$ 分成了一组，那么我们可以把 $L_1$ 挪到 $L_2$ 那一组， $L_2$ 那组的贡献不会变，但是 $L_3$ 单独成组更优了。

于是我们把包含其他线段的先取出来，那么剩下的线段左右端点都是单增的。显然有结论：在剩下的线段里一定是连续的一段成一组。那么有 dp： $dp_{i,j}$ 表示分了 $i$ 段，第 $i$ 段结尾是 $j$ 的最大贡献。于是我们有转移：

dp_{i,j} = \max_{k = 0}^{j - 1}\{dp_{i - 1,k} + \max(0,r_{k + 1} - l_j)\}

用前缀和优化即可。

哈希。

尝试驯服可持久化字典树。

成功驯服，耗时 1h。

死因：root[maxn << 1] 写成了 root[maxn]

我爸曾经给我说过，他上高中的时候走路都在想题，专心的甚至能装到墙上去。

我现在懂了：只有没朋友的人才会那样，因为他们下课没事干只能思考。