题解：CF1699C The Third Problem

· · 题解

似乎没有题解写过这种做法。

首先对于排列，我们有一个性质：\text{mex}_{i=1}^x p_i=\min_{i=x+1}^n p_i。

考虑这个性质有什么用，发现它可以锁定所有前缀最小值 pre_i，后缀最小值 suc_i，即问题转化为：给定所有 pre_i,suc_i，求有多少个合法的排列。

显然我们一定可以锁定一些位置的值：如果 pre_i \neq pre_{i-1}，那么一定有 p_i=pre_i；如果 suc_i \neq suc_{i+1}，那么一定有 p_i=suc_i。

对于剩下的不能确定值的位置，它应该满足 p_i>\max(pre_i,suc_i)，考虑把所有这样的 \max(pre_i,suc_i) 拎出来从大到小排序，乘法原理计算方案数即可。

时间复杂度 \text{O}(n \log n)，瓶颈在排序。

link