题解

思路

最大值 $n$ 同时是最后一个前缀最大值和第一个后缀最大值，所以必须有 $p_1=1$、$s_{m_2}=n$ 且 $p_{m_1}=s_1$。设这个共同位置为 $x$。

做法

先用 $\binom{n-1}{x-1}$ 选择放在最大值左侧的数。对于相邻前缀最大值位置 $p_i,p_{i+1}$，令间隔中的普通位置数为 $d=p_{i+1}-p_i-1$。从右向左处理记录位置时，可从当前仍可使用且比新记录小的数中有序选择 $d$ 个，贡献为组合数乘 $d!$。右侧完全对称，从左向右处理后缀最大值位置。

$n\le9$ 时可枚举全部排列；$n\le2000$ 时可用 Pascal 递推预处理组合数；满分做法预处理阶乘与逆阶乘，在常数时间查询组合数。

正确性说明

必要条件保证全局最大值位置一致。选定左右两侧的值集合后，左右条件互不影响。每一段普通位置必须放入比其相邻记录值更小的数；组合数选择这些数，阶乘排列它们。逆序处理前缀记录、正序处理后缀记录时，每个位置和值恰被选择一次，因此乘积无重无漏地计数全部合法排列。

复杂度

满分算法预处理后每组为 $O(m_1+m_2)$，总时间 $O(\sum n)$，空间 $O(\max n)$。