题解：P16433 [APIO 2026 中国赛区] 上升

· · 题解

赛时这个题从开场做到一点四十五，然后第二题 8 分，故有这个题解。

考虑简单的东西，特殊性质 A。

算法一：

设 dp_{i,j} 表示填了前 i 个数，最后一个数在这些数是第 j 小的，即插入法。

算法二：

分成若干个下降段，然后组合数和容斥，即组合数。

看到这些填排列的，算法一是常见的，另外我们可以把算法二和延迟贡献（详见 员工招聘）结合。

于是我们最后的做法必然是这两种算法一种的扩展或者融合而成。

经思考，单独某个算法很难做。

我们考虑算法二和延迟贡献结合更难，在算法二上参考一些算法一。

设 dp_{i,j} 表示考虑了前 i 个数，设下一个固定的数是 p，比它小的我们说是白色，比它大的是黑色，为了因为前 i 个数，p 单调增，于是黑色可能变为白色，利用延迟贡献思想，我们暂时不考虑黑色数贡献，等它变白再贡献，白色则必须贡献。

不过不贡献不是完全不贡献，我们需要让所有黑数和白数内部确定顺序，也就是说当前的数任意两个的大小关系需要得到。

因为 w_i 根据上升确定，于是我们有必要知道上一个数的相对顺序。

我们不能只用插入的原因在于我们难以要求填的数真的是那个大小，插入会让固定数难以保持。

我们为了解决这个问题，我们需要确定所有白数的真实大小，这样我们填的时候不会影响前面固定的。

另外，我们需要上一个数是谁。

设 dp_{i,j,k} 表示表示考虑前 i 个数，并且已经选了 j 个白数（含固定），若 k\le j+1，则上一个是白数，并且考虑剩下的没填写的白数，在上一个数填写之前是第 k 小的没填的白数。

当 k>j+1 时，表示上一个数是黑数，且在黑数中相对大小为第 k-j-1 小。

我们惊讶的发现能转移了。

每次遇到普通数，就枚举 k 和当前数插入后的 k，容易讨论黑白和相邻两个数相对大小。

另外，如果是固定数，那么考虑枚举黑的一些最小的数变白，容易计算。

复杂度 O(n^4)。

对于前者，观察转移式，容易差分优化。

对于后者，考虑当前这个数必然白，且在新白中相对大小通过黑转白个数容易统计。

我们并不关心之前 k 具体大小，只关心黑白，于是合成后只需要 O(n^3)。

卡常：取模是万恶的，能减少就减少，只要在复杂度瓶颈处减少取模个数常数，优化很大。

代码之后再放吧。