P11164 [BalkanOI 2023] Permutations 题解

考虑先判无解。容易发现无解当且仅当 $p_L,p_{L+1},\ldots,p_R$ 中存在位置 $i,j,k$ 满足 $p_i>p_j>p_k$，或存在位置 $i,j$ 满足 $p_i>p_j$ 且区间外存在元素 $x$ 满足 $x<p_j$。第一类情况可以对每个位置 $j$ 用单调栈预处理出 $L_j=i,R_j=k$ 然后判断是否有 $\forall j,l\le L_j\le R_j\le r$ 即可；第二类情况对每个 $j$ 找到最靠右的位置 $i$ 然后把信息挂在 $i$ 上对 $j$ 做扫描线即可 $O(n\log n)$ 判定。

然后考虑计数。直接做原问题是困难的，先弱化问题，计数 $1\sim n$ 的排列中 LDS 长度不超过 $2$ 的排列数量。容易想到按值插入做 dp。设 $f_{i,j}$ 表示当前处理到了值 $i$，第一个能放更大的数的位置是 $j$ 的排列方案数。转移就是 $f_{i,j}$ 可以转移到 $f_{i+1,k}$ 当且仅当 $k\in[j,i+1]$。给这个东西编一个组合意义就是从 $(1,1)$ 走到 $(n+1,n+1)$，每一次只能向右或向上走，且不能触碰直线 $y=x+1$ 的方案数。这个东西就是一个标准单线反射容斥形式。

然后回到原问题。容易发现此时序列中没有出现过的值不超过 $\max\limits_{i=L}^Rp_i$ 的数必须升序排列，因此出发点就从 $(1,1)$ 移动到了 $(\max\limits_{i=L}^Rp_i,R-L+2)$，同样可以单线反射容斥算答案为 $\binom{2n-\max\limits_{i=L}^Rp_i-(R-L+1)}{n-\max\limits_{i=L}^Rp_i}-\binom{2n-\max\limits_{i=L}^Rp_i-(R-L+1)}{n-\max\limits_{i=L}^Rp_i-1}$，预处理阶乘和阶乘逆即可 $O(n)-O(1)$ 算答案。

总时间复杂度为 $O(n\log n)$，瓶颈在于判无解的时候需要在扫描线过程中用线段树 / BIT 维护信息。