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

山田リョウ · 2026-05-11 14:07:08 · 题解

钦定 >，这样好处是钦定的连续段内最多一个事先确定的位置（因为事先确定的位置的值是递增的），然后一个空隙被钦定 > 了就带 1-w_i 的权，否则是 w_i 的权，这样配出来刚好是对的（道理其实是你先全除以 w_i，然后 > 的位置带权 x_i 的话得到的是 \prod_i(x_i+1)）。

那你现在做的是，把一堆有标号点划分到有标号集合里（因为你本身限制了一段内有序，所以就当做集合来看），但是特别的，因为有关键点，对于某些集合你要求所有元素 >x，有些集合要求所有元素 <x，有的无限制。对集合中所有元素 >x 做二项式反演，转成钦定 k 个 <x，其余无限制，带 (-1)^k\binom{l}{k} 的权，然后注意到扫的过程中 x 递增，也就是如果优先为 <x 的这些位置选择值，你是能确定出还有多少位置能选的，记录下当前有多少个无限制的最后再一起选择就行。于是你直接从左往右扫，记录下有多少无限制的位，状态量是 \mathcal{O}(n^2) 的，转移是枚举上一段结尾因此总复杂度 \mathcal{O}(n^3)。