题解：P16433 [APIO 2026 中国赛区] 上升
CarroT1212
·
·
题解
好像过的人比想象中少很多，发一下我场上的直接 DP 做法。
考虑 DP 从前到后插数的过程。定点是逐渐上升的，那么经过了 csp t4 洗礼的大家就可以往贡献延迟计算的方向思考一下。
大致的状态设计思路是，假设现在已经插完了 [1,i]，最新的一个定点的值是 lst，我们把目前已经插入的数中，值 \le lst 的称为小数，>lst 的称为大数。对于这些 >lst 的大数，我们暂时不管它们跟后面的定点之间的大小关系，而是在 i 遍历到一个新定点的时候才把当前最小的若干个大数分配到 lst 和新定点中间的值域里。
同时计数的时候我们要想办法记一下第 i 个数的大小，用来处理插数时出现的 w 的贡献。
先掰扯一下怎么想到状态设计的细节，觉得太臭可以直接跳过。
:::info[阿巴阿巴]{open}
对于这种排列插数问题，我们会倾向于维护当前这些数的相对顺序，插入就直接在相邻两个值的缝里插，这样就容易表示当前的大小关系。但是在这个题里我们肯定不能对 <lst 的部分这么干。因为你已经把 lst 之前的定点信息都抛弃了，如果只管小数的相对顺序的话很可能会把前面已经处理完的定点挤开。
所以对于 \le lst 的部分，我们需要直接在每个“小数”出现的时候就把它的值定下来，而不是维护相对顺序。实际 DP 就是记录当前 [1,lst] 值域内有多少个没填过的值，称为空位，插数的时候就填进这些空位里。
对于 >lst 的部分，由于暂时不能处理 i 后面更大的定点，所以还是维护当前这些大数的相对顺序。
:::
相信有了这个思路之后大家应该能编出一个正确的 DP 了，考虑到本题主要难点在于找到一个简洁的写法并且调对它，所以接下来的一大段内容会用来详细写一下我干了啥。
+ 如果 $0\le j\le t$，就表示第 $i$ 个数是一个小数，或者说是一个刚刚被填上的空位（特别地，如果 $i$ 是一个定点的话我们也把它当作被填上的空位），它的值在**现在**的第 $j$ 个空位和第 $j+1$ 个空位之间（如果 $j=0$ 或 $j=t$，就表示它比现在的所有空位都小/大，但是没有超过 $lst$）；
+ 如果 $j>t$，那么第 $i$ 个数是大数，它是当前的大数中第 $j-t$ 小的。
考虑 $i-1\to i$ 的转移。如果 $i$ 不是定点，我们枚举新插的数插在哪里，假设它在所有能插的位置中插了第 $k$ 小的那个，具体来说：
+ 如果 $1\le k\le t$，说明插在了当前第 $k$ 个空位里；
+ 如果 $t<k\le t+cnt+1$（$cnt$ 表示前 $i-1$ 个数的大数个数，也就是 $i-1-(t-j)$），说明插在了第 $k-t-1$ 和 第 $k-t$ 个大数中间（对于 $k=t+1$ 和 $k=t+cnt+1$，表示插在了比所有大数都小/大的位置，但是仍然 $>lst$。
+ 我们定义这么大一坨东西的好处就是，可以发现，不管是不是大数小数，**只要 $k>j$ 就说明这个新插的数比上一个数要大，$k\le j$ 就说明更小**。所以转移的时候我们很容易就能处理 $w_{i-1}$ 是否贡献进答案里。
（之后应该会在这里补一张图形象地展示一下 $j$ 和 $k$ 的关系）
如果第 $i$ 个数是定点，那就要先像前面说的那样枚举一下要把多少个大数下放到小数去，得到一组新的状态。假设新的定点值是 $lst'$，那就相当于把这些新的小数固定在 $(lst,lst')$ 内，$(lst,lst']$ 剩下的地方就变成了空位，转移要乘一个分配空位的组合数。然后对这个新的状态插入这个定点。
实际上插入这个定点可以视为，我们强制把第 $i$ 个数插在了 $k=t$ 的空位，然后就可以做和上面非定点一样的转移了。
总之就是要枚举 $i,t,j,k$，而所有枚举 $k$ 的部分都容易前缀和优化，所以就做到了 $O(n^3)$（枚举把多少个大数下放到小数时由于枚举总量是 $O(n)$ 的所以也没问题），常数不大。比较复杂的细节可以瞅一下代码，写出来还挺好看。
但这玩意在考场上真的非常难调，所以还是有必要搞个暴力手搓点数据对照一下的。赛时在本题砸了约 2h。
:::success[$O(n^4)$]
电脑没电了，今晚补上。
:::
:::success[$O(n^3)$]
电脑没电了，今晚补上。
:::