11.1 联测

A

设 $f_n$ 表示 $n$ 时的答案。（无解时 $f_n=inf$）。

不难发现 $f_n$ 是递增的，考虑直接 dp 求解。

先考虑填表法，暴力枚举每个 $a_i$，然后 $f_{\frac{n}{a_i}a_i}+1 \rarr f_n$。

没有优化空间啊，考虑刷表法，枚举 $f_n+1 \rarr f_{n+j},j\in[1,p-1]$。

发现 $p$ 取 $\max_{a_i|n}a_i$ 时一定最优，设为 $d_i$。$d_i$ 可以用埃筛的方式预处理。

现在能做 $O(V\log V)$ 了，继续优化。

由于 $f_n=i$ 的 $n$ 一定构成一个连续段，考虑维护这个连续段 $[l,r]$。

每次 $l' \larr r+1,r' \larr \max_{i\in[l,r]}d_i$。

这样可以做到 $O(V)$ 预处理，$O(1)$ 回答询问。

B

如果给定 $a$，$l_i,r_i$ 可以用单调栈求出。

注意到打乱后的 $\{l'\},\{r'\}$ 一定唯一对应一个 $\{l\},\{r\}$。

证明：考虑每个 $i$ 在 $r'$ 中的出现次数 $t_i$，发现 $t_i$ 即是扫到 $i$ 是单调栈的弹出次数。

单调栈在任意时刻的状态确定，$\{l\},\{r\}$ 也就唯一确定了。

现在问题等价于，给定笛卡尔树的形态，求标号方法（或者说拓扑序）。

这个的方案数是 $n!\prod siz_i$。