P11164 [BalkanOI 2023] Permutations

思路

先判断是否有解。
即判断区间是否存在三元组 \((p_i,p_j,p_k)(i < j < k)\) 使得 \(p_i > p_j > p_k\)；或者二元组 \((p_i,p_j)(i p_j > \min_{k=1}^{L-1} \min_{k=R+1}^{n} \space p_k\)。
贪心的覆盖区间，三元组对于 \(j\) 我们只找最靠右的 \(i\) 和最靠左的 \(k\)；二元组对 \(j\) 只找最靠右的 \(i\)。扫描线一遍 \(j\)，把权值都挂在 \(i\) 上维护即可。
然后求方案数。
先考虑一个弱化问题：将 \(1\sim n\) 的排列 \(P_n\) 放成最长递减子序列长度至多为二，共有多少种方案。
考虑一种类似维护连续段的转移，把序列按点 \((i,p_i)\) 摊到平面上，称 \(p_{i-1} > p_i < p_{i+1}\) 为一个“谷”。
设 \(f_{i,j}\) 表示放完前 \(i\) 个数，最后一个“谷”在 \(j\) 的方案数。
发现我们新插入数只能是使最后一个“谷”向右移动，或者拼接在段的右端点上，即 \(f_{i,j}\) 会贡献给 \(\sum_{k=j}^{i+1} f_{i+1,k}\)。
在转移状态的平面上看这个方程，发现我们转移的路径是每次从当前层先到下一层，到下一层后可以选择向右转移若干状态或者不动。把这件事看成网格图上走路，每次必须向上走一步，然后可以选择向右走一些格子。每次选择是否向右走，以及向右走几格，对应方案与从 \((1,1)\) 走到 \((n+1,n+1)\) 的路径相对应。当 \(j>i\) 时状态无意义，即不能越过直线 \(y = x\)。
回到原问题。
令 \(mx = \max_{i=L}^{R} \space p_i\)。小于 \(mx\) 的数一定按升序放，而剩下的大于 \(mx\) 的数在小于 \(mx\) 的数放完前需要升序放。
这与我们刚才在网格图上走路的方式很像。
令 \(Len = R-L+1\)，考虑共剩下 \(n-Len\) 个数，其中小于 \(mx\) 的有 \(mx-Len\) 个，大于 \(mx\) 的数有 \(n-mx\) 个。
然后像网格图上走路一样刻画放数的过程，走的步数与大于和小于 \(mx\) 的数的个数向对应。即相当于从 \((mx,Len)\) 走到 \((n,n)\) 不越过 \(y=x\)。
按 \(y=x+1\) 对称，反射容斥一下，答案为 \(C_{2n-mx-Len}^{n-Len} - C_{2n-mx-Len}^{n-Len+1}\)。
代码

[code]#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;typedef long long ll;typedef unsigned long long ull;template inline void read(T&x){        int w = 0; x = 0;        char ch = getchar();        while(ch'9'){                if(ch=='-') w = 1;                ch = getchar();        }        while(ch>='0' && ch