我们发现我们第一问的 slope trick 优化 dp 的流程相当于是解决如下问题：维护一个集合 S，初始为空。按 b_i 从小到大排好序后，从前往后扫，每次先执行 b_i 步若 S 不为空则从 S 中选择一个数并将其减 1，减到 0 后就扔出集合。然后将 a_i 加入集合。最后还可以再执行任意多步上述减 1 操作。f(a,b,k) 即为删去 k 个数最少需要多少步。显然每次贪心地让最小的数减 1 是最优的。
当确定 a 时没有一个简洁形式的答案表示 f(a,b,k)。于是我们考虑直接将贪心过程压进 dp：依旧从前往后扫，每往集合中加入一个数时钦定其是否会被扔掉。我们需要贪心地去钦定：若当前加入的数不小于集合中一个未被钦定的数，则这个数必须不能被钦定；若当前加入的数小于集合中的一个被钦定的数，则这个数必须被钦定。否则会重复计算。于是我们设计出如下状态：dp_{i,j,k,u,w} 表示考虑了前 i 个数，钦定了 j 个，当前被钦定的数之和为 k，最大的为 u，未被钦定的最小的数为 w。转移时枚举当前 a_i，枚举其是否被钦定，时间复杂度为 O(n^3V^4)，使用前缀和优化可做到 O(n^3V^3)。
upd：感觉可以做到 O(n^3V^2)，不过只是口胡，没有写，不知道有没有假。
2023-2024 集训队互测 Round 5 T2 栞
submission
木柜子乐队好评
题目比较简单。
首先考虑将 q 划分成 k 个上升子段，然后将每个上升子段打乱得到原排列 p。我们考虑怎样才是合法的。对于一个确定的 p 我们有如下贪心过程：若 k=1 则将排列排序并退出，否则取出其前 n-k+1 个数并排序，找到其最小的前缀满足其中所有数在 p 中出现的位置也是一个前缀，取出这个前缀作为第一段并递归到 k-1。
考虑 dp：令 dp_{i,j} 表示使用了 q 中的前 i 个数，划分成了 j 段的答案。这样做我们发现 dp_{i,j} 会对之后的数有限制。具体地，如果 q 中第 u 段结尾的数为 end_u，那么要求 p 在 [i+1,n-k+u] 中的数全部 >end_u（否则与前面所述的贪心过程矛盾）。我们发现若当前剩余段的长度不必全都是 1（即 n-k+j>i+1），则下一段（第 j+1 段）结尾的数必然大于第 j 段结尾的数。也就是说，end_u 单调递增，因此只用考虑第 j 段带来的限制。我们枚举下一个 q 上的单增段，设其长度为 len，共 x 个数比 end_u 小。若 x=0，则其贡献为长度为 len 且【不存在前缀是排列】的排列个数，预处理即可；若 x>0，则贡献非零当且仅当 x=1 且当前段为 [i+1,n-k+j]，其贡献就是一个阶乘。