CF2056E Nested Segments

· · 题解

CF2056E Nested Segments

注意到最优构造会是一个二叉树（线段树？）状物，答案为 2n - 1。

证明可以考虑归纳。设 f _ n 为 [1, n] 的答案，然后大致就是，首先选择 [1, n]，然后随便选一个 x 分为两段 [1, x] 和 [x + 1, n]，变成两个子问题，f _ n = 1 + f _ {x} + f _ {n - x} = 1 + 2x - 1 + 2(n - x) - 1 = 2n - 1；而分成更多段的时候，算一下这个值会 < 2n - 1。

考虑当 m = 0 时求最优构造的方案数。

设为 g _ n。发现 x 可以任意选取，于是 g _ n = \sum _ {i = 1} ^ {n - 1} g _ i g _ {n - i}。这不是卡特兰数吗，所以得到了 g _ {n + 1} = H _ n = \frac {\binom {2n} {n}} {n + 1}。

那当 m \neq 0 时呢。

发现 [1, n] 和 [i, i] 都是一定选取的，把他们加进来，发现区间之间可以按照包含关系建出一个树状结构。

考虑结点 u 表示区间 [l _ u, r _ u]，设它有 deg _ u 个子结点。不难发现这一步选取的区间，不能跨越两个子结点的区间内部，就是可以把一个子结点 [l _ v, r _ v] 当作一个点 [x, x]，于是实际上变成了一个 deg _ u 规模的 m = 0 的问题，方案数是 H _ {deg _ u - 1}。

预处理 H _ n，排序后用一个单调栈建树，答案为 \prod H _ {deg _ u - 1}。

时间复杂度为 O(\log n)。

代码。