自动搬运

查看原文

来自洛谷，原作者为

	紊莫 ?？?

搬运于2025-08-24 23:08:13，当前版本为作者最后更新于2025-04-22 07:30:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

结论：建立析合树，若存在析点，答案为 $0$，否则答案为 $\prod \mathrm{Catalan}(|son_u|-1)$。

首先将题意稍微转化一下，先确定每一层的划分，然后每次的 rand_int(0,1) 就不用管了，显然能生成 $P$ 的方案唯一。

然后将点重新标号一下，从 $[1,n]$ 上划分出 $P$ 变成 $P$ 中划分出 $[1,n]$，显然答案不变。

对于 $P$ 已经排好序的情况，每一次的划分都没有限制，设 $f_i$ 表示长度为 $i$ 的序列的划分方案，枚举第一次划分有：

这就是经典的卡特兰数，所以 $f_i = \mathrm{Catalan}(i-1)$。

然后考虑暴力的算法，如果直接仿照上面的 DP，时间复杂度会达到 $O(n^3)$。

转而考虑原序列的本原连续段，一个连续段的定义是 $[l,r]$ 表示在 $p_l,\dots,p_r$ 内值域是一个连续的区间，而本原连续段就是不存在与之相交却无包含关系的连续段的连续段。

取出所有这样的连续段，将其建成一棵树，这个树即析合树。

现在，我们首先说明存在析点（儿子序列的任意子区间都不是连续段）就无解。

对于这一次划分，首先不能从一个儿子的区间中分开，否则就和本原连续段的定义矛盾。因为析点的性质，导致其不存在任意一个合法的划分，答案即为 $0$。

然后对于一个合点（儿子是正序或者逆序），同样的不能从一个儿子的区间中分开，把这些段看成一个点，那么就是首先任意建立这些点的二叉树，最后再从每个点递归下去。

于是答案是卡特兰数之积的形式也比较显然了。